Prime Arrangements

Return the number of permutations of 1 to n such that prime numbers are at prime indices (1-indexed). Answer modulo 10^9+7.

Example 1

Input: 5 → Output: 12

Example 2

Input: 100 → Output: 682289015

Solution Approach

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.

Java

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)