Return the number of permutations of 1 to n such that prime numbers are at prime indices (1-indexed). Answer modulo 10^9+7.
Input: 5 → Output: 12Input: 100 → Output: 682289015
Count primes up to n (call it p). Non-primes = n - p. Answer = p! * (n-p)! mod 10^9+7.
- Count primes up to n using Sieve of Eratosthenes.
- Compute primes! * (n-primes)! mod 10^9+7.
class Solution {
static final long MOD = 1_000_000_007;
public int numPrimeArrangements(int n) {
int primes = countPrimes(n);
return (int)(factorial(primes) * factorial(n - primes) % MOD);
}
private int countPrimes(int n) {
boolean[] comp = new boolean[n+1];
int count = 0;
for (int i = 2; i <= n; i++) {
if (!comp[i]) { count++; for (int j = 2*i; j <= n; j += i) comp[j] = true; }
}
return count;
}
private long factorial(int n) {
long res = 1;
for (int i = 2; i <= n; i++) res = res * i % MOD;
return res;
}
}
- Time Complexity: O(N log log N)
- Space Complexity: O(N)