# 1175. Prime Arrangements

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: int numPrimeArrangements(int n) { constexpr int kMod = 1'000'000'007; const int count = countPrimes(n); return (factorial(count, kMod) * factorial(n - count, kMod)) % kMod; } private: int countPrimes(int n) { vector prime(n + 1, true); prime[0] = false; prime[1] = false; for (int i = 0; i <= sqrt(n); ++i) if (prime[i]) for (int j = i * i; j <= n; j += i) prime[j] = false; return count(begin(prime), end(prime), true); } long factorial(int n, const int kMod) { long fact = 1; for (int i = 1; i <= n; ++i) fact = fact * i % kMod; return fact; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public int numPrimeArrangements(int n) { final int kMod = 1_000_000_007; final int count = countPrimes(n); return (int) ((factorial(count, kMod) * factorial(n - count, kMod)) % kMod); } private int countPrimes(int n) { boolean[] prime = new boolean[n + 1]; Arrays.fill(prime, 2, n + 1, true); for (int i = 0; i * i <= n; ++i) if (prime[i]) for (int j = i * i; j <= n; j += i) prime[j] = false; int count = 0; for (boolean p : prime) if (p) ++count; return count; } long factorial(int n, final long kMod) { long fact = 1; for (int i = 1; i <= n; ++i) fact = fact * i % kMod; return fact; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def numPrimeArrangements(self, n: int) -> int: kMod = 1_000_000_007 def countPrimes(n: int) -> int: isPrime = [False] * 2 + [True] * (n - 1) for i in range(2, int(n**0.5) + 1): if isPrime[i]: for j in range(i * i, n + 1, i): isPrime[j] = False return sum(isPrime) def factorial(n: int) -> int: fact = 1 for i in range(1, n + 1): fact = fact * i % kMod return fact count = countPrimes(n) return factorial(count) * factorial(n - count) % kMod