Prime Arrangements

Intuition

Solution

class Solution:
    def isPrime(self, n):
        if n == 1:
            return False
        for i in range(2, n // 2 + 1):
            if n % i == 0:
                return False
        return True

    def numPrimeArrangements(self, n: int) -> int:
        count = 0
        mod = 10 ** 9 + 7
        for i in range(1, n + 1):
            if self.isPrime(i):
                count += 1
        non_count = n - count
        ans = 1
        while count > 1:
            ans = (count * ans) % mod
            count -= 1
        while non_count > 1:
            # ans *= non_count
            ans = (non_count * ans) % mod
            non_count -= 1
        return ans % mod