1175.md

1175. Prime Arrangements

Solution 1 (time O(n^(3/2)), space O(1))

class Solution(object):
    def numPrimeArrangements(self, n):
        """
        :type n: int
        :rtype: int
        """
        def is_prime(n):
            if n == 1:
                return 0
            for i in range(2, int(sqrt(n)) + 1):
                if n % i == 0:
                    return 0
            return 1

        mod = 10 ** 9 + 7
        num_primes = sum(is_prime(i) for i in range(1, n + 1))
        ans = 1
        for i in range(1, num_primes + 1):
            ans = (ans * i) % mod
        for i in range(1, n - num_primes + 1):
            ans = (ans * i) % mod
        return ans