Prime Arrangements

Problem

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Examples

Example 1:

1
2
3
4
5


Input:
n = 5
Output:
 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

1
2
3
4


Input:
n = 100
Output:
 682289015

Solution

Method 1 – Prime Counting and Factorial Product

Intuition

The key idea is that the only way to satisfy the condition is to place all primes at prime indices and all non-primes at non-prime indices. The number of ways to arrange the primes among the prime indices is the factorial of the number of primes, and similarly for non-primes.

Approach

Count the number of primes up to n (let’s call it p).
The number of non-primes is n - p.
The answer is p! * (n-p)! modulo 10^9 + 7.
Use the Sieve of Eratosthenes to efficiently count primes.
Compute factorials modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int numPrimeArrangements(int n) {
        int mod = 1e9 + 7;
        vector<bool> isPrime(n+1, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) isPrime[j] = false;
            }
        }
        int p = 0;
        for (int i = 2; i <= n; ++i) if (isPrime[i]) ++p;
        long long ans = 1;
        for (int i = 2; i <= p; ++i) ans = (ans * i) % mod;
        for (int i = 2; i <= n - p; ++i) ans = (ans * i) % mod;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func numPrimeArrangements(n int) int {
    mod := int(1e9 + 7)
    isPrime := make([]bool, n+1)
    for i := 2; i <= n; i++ { isPrime[i] = true }
    for i := 2; i*i <= n; i++ {
        if isPrime[i] {
            for j := i * i; j <= n; j += i {
                isPrime[j] = false
            }
        }
    }
    p := 0
    for i := 2; i <= n; i++ {
        if isPrime[i] { p++ }
    }
    ans := 1
    for i := 2; i <= p; i++ { ans = ans * i % mod }
    for i := 2; i <= n-p; i++ { ans = ans * i % mod }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    public int numPrimeArrangements(int n) {
        int mod = 1000000007;
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) isPrime[j] = false;
            }
        }
        int p = 0;
        for (int i = 2; i <= n; i++) if (isPrime[i]) p++;
        long ans = 1;
        for (int i = 2; i <= p; i++) ans = ans * i % mod;
        for (int i = 2; i <= n - p; i++) ans = ans * i % mod;
        return (int)ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    fun numPrimeArrangements(n: Int): Int {
        val mod = 1_000_000_007
        val isPrime = BooleanArray(n+1) { true }
        isPrime[0] = false; isPrime[1] = false
        for (i in 2..n) {
            if (isPrime[i]) {
                var j = i * i
                while (j <= n) {
                    isPrime[j] = false
                    j += i
                }
            }
        }
        var p = 0
        for (i in 2..n) if (isPrime[i]) p++
        var ans = 1L
        for (i in 2..p) ans = ans * i % mod
        for (i in 2..(n-p)) ans = ans * i % mod
        return ans.toInt()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        mod = 10**9 + 7
        is_prime = [True] * (n+1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, int(n**0.5)+1):
            if is_prime[i]:
                for j in range(i*i, n+1, i):
                    is_prime[j] = False
        p = sum(is_prime)
        ans = 1
        for i in range(2, p+1):
            ans = ans * i % mod
        for i in range(2, n-p+1):
            ans = ans * i % mod
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


impl Solution {
    pub fn num_prime_arrangements(n: i32) -> i32 {
        let n = n as usize;
        let mut is_prime = vec![true; n+1];
        is_prime[0] = false;
        is_prime[1] = false;
        for i in 2..=((n as f64).sqrt() as usize) {
            if is_prime[i] {
                let mut j = i * i;
                while j <= n {
                    is_prime[j] = false;
                    j += i;
                }
            }
        }
        let p = is_prime.iter().filter(|&&x| x).count();
        let mut ans: i64 = 1;
        let m = 1_000_000_007;
        for i in 2..=p { ans = ans * i as i64 % m; }
        for i in 2..=(n-p) { ans = ans * i as i64 % m; }
        ans as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    numPrimeArrangements(n: number): number {
        const mod = 1e9 + 7;
        const isPrime = Array(n+1).fill(true);
        isPrime[0] = isPrime[1] = false;
        for (let i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (let j = i * i; j <= n; j += i) isPrime[j] = false;
            }
        }
        let p = 0;
        for (let i = 2; i <= n; i++) if (isPrime[i]) p++;
        let ans = 1;
        for (let i = 2; i <= p; i++) ans = ans * i % mod;
        for (let i = 2; i <= n - p; i++) ans = ans * i % mod;
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n log log n) for the sieve, and O(n) for factorials, so overall O(n).
🧺 Space complexity: O(n) for the sieve array.

Problem#

Examples#

Solution#

Method 1 – Prime Counting and Factorial Product#

Intuition#

Approach#

Code#

Complexity#