[Python] Sieve of Eratosthenes
\nclass Solution:\n    def numPrimeArrangements(self, n: int) -> int:\n        prime = [True for _ in range(n + 1)]\n        p = 2\n        while p * p <= n:\n 
```\nclass Solution:\n    def numPrimeArrangements(self, n: int) -> int:\n        prime = [True for _ in range(n + 1)]\n        p = 2\n        while p * p <= n:\n            if prime[p]:\n                for i in range(p * p, n + 1, p):\n                    prime[i] = False\n            p += 1\n        primes = sum(prime[2:])\n        return math.factorial(primes) * math.factorial(n - primes) % (10 ** 9 + 7)\n```\n* Cheat\n```\nclass Solution:\n    def numPrimeArrangements(self, n: int) -> int:\n        primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]\n        cnt = bisect.bisect(primes, n)\n        return math.factorial(cnt) * math.factorial(n - cnt) % (10 ** 9 + 7)\n```\n
[]