# Prime Arrangements
**Difficulty:** EASY
[External](https://leetcode.com/problems/prime-arrangements)
Canonical: https://scaleengineer.com/dsa/problems/prime-arrangements
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## 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`**.

**Example 1:**

**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:**

**Input:** n = 100
**Output:** 682289015

**Constraints:**

* `1 <= n <= 100`

# Approaches
## Brute Force with Naive Primality Test
This approach directly implements the mathematical formula derived from the problem's constraints. The core idea is to separate the numbers and indices into two groups: prime and non-prime. The number of valid permutations is the product of the permutations of primes within prime indices and the permutations of non-primes within non-prime indices. It uses a simple, but inefficient, method to check for prime numbers.
**Time:** O(n^2). The primality test for each number up to `n` takes O(n) time, and we do this for `n` numbers. The factorial calculations take O(n) time, which is dominated by the prime counting part. · **Space:** O(1). We only use a few variables to store counts and intermediate results.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** The primality test is very inefficient, with a time complexity of O(n) for each number.; Overall time complexity is poor and would be too slow for larger values of `n`.
### Explanation
First, we need to determine the number of prime numbers between 1 and `n`. Let's call this `primeCount`. We can find `primeCount` by iterating through each number `i` from 2 to `n` and checking if it's prime. A naive primality test for a number `x` involves checking for divisibility by all integers from 2 up to `x-1`.

The number of non-prime numbers will be `n - primeCount`. The problem now reduces to arranging `primeCount` prime numbers in `primeCount` available prime-indexed slots, and `n - primeCount` non-prime numbers in the remaining `n - primeCount` non-prime-indexed slots.

The number of ways to arrange `k` items is `k!` (k factorial). Therefore, the total number of valid permutations is `(primeCount!) * ((n - primeCount)!)`. Since the result can be very large, all calculations, especially the factorials, must be performed modulo `10^9 + 7`. We calculate the factorials iteratively, applying the modulo at each multiplication step to prevent overflow.

```java
class Solution {
    public int numPrimeArrangements(int n) {
        long MOD = 1_000_000_007;
        int primeCount = 0;
        for (int i = 1; i <= n; i++) {
            if (isNaivePrime(i)) {
                primeCount++;
            }
        }
        int nonPrimeCount = n - primeCount;
        long ans = factorial(primeCount, MOD);
        ans = (ans * factorial(nonPrimeCount, MOD)) % MOD;
        return (int) ans;
    }

    private boolean isNaivePrime(int num) {
        if (num <= 1) {
            return false;
        }
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    private long factorial(int k, long MOD) {
        long res = 1;
        for (int i = 2; i <= k; i++) {
            res = (res * i) % MOD;
        }
        return res;
    }
}
```
### Algorithm
- Initialize `primeCount` to 0.
- Iterate from `i = 1` to `n`.
- For each `i`, check if it's a prime number using a naive primality test (checking divisibility from 2 to `i-1`).
- If `i` is prime, increment `primeCount`.
- Calculate `nonPrimeCount = n - primeCount`.
- Calculate `factorial(primeCount)` modulo `10^9 + 7`.
- Calculate `factorial(nonPrimeCount)` modulo `10^9 + 7`.
- The result is the product of the two factorials, also taken modulo `10^9 + 7`.

## Optimized Primality Test
This approach improves upon the brute-force method by using a more efficient primality test. The overall logic of counting primes, calculating factorials, and combining the results remains the same. The key optimization is in how we determine if a number is prime.
**Time:** O(n * sqrt(n)). We iterate `n` times, and each primality test takes up to O(sqrt(n)) time. · **Space:** O(1). No extra space proportional to `n` is used.
**Pros:** More efficient than the naive approach.; Still relatively simple to implement and requires no extra space.
**Cons:** While better than the naive approach, it is still not the most optimal method for finding all primes up to `n`.
### Explanation
The core improvement lies in the `isPrime` function. A number `x` is not prime if it has a divisor other than 1 and itself. If `x` has a divisor `d`, then `x = d * (x/d)`. One of these factors must be less than or equal to `sqrt(x)`. Therefore, to check if `x` is prime, we only need to check for divisibility by numbers from 2 up to `sqrt(x)`. This significantly reduces the number of checks compared to the naive approach.

The rest of the algorithm is identical:
1. Count the number of primes up to `n` using the optimized `isPrime` function.
2. Calculate `primeCount` and `nonPrimeCount`.
3. Compute `(primeCount!) * ((n - primeCount)!)` modulo `10^9 + 7`.

```java
class Solution {
    public int numPrimeArrangements(int n) {
        long MOD = 1_000_000_007;
        int primeCount = 0;
        for (int i = 1; i <= n; i++) {
            if (isOptimizedPrime(i)) {
                primeCount++;
            }
        }
        int nonPrimeCount = n - primeCount;
        long ans = factorial(primeCount, MOD);
        ans = (ans * factorial(nonPrimeCount, MOD)) % MOD;
        return (int) ans;
    }

    private boolean isOptimizedPrime(int num) {
        if (num <= 1) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    private long factorial(int k, long MOD) {
        long res = 1;
        for (int i = 2; i <= k; i++) {
            res = (res * i) % MOD;
        }
        return res;
    }
}
```
### Algorithm
- Initialize `primeCount` to 0.
- Iterate from `i = 1` to `n`.
- For each `i`, check if it's a prime number using an optimized primality test (checking divisibility from 2 to `sqrt(i)`).
- If `i` is prime, increment `primeCount`.
- Calculate `nonPrimeCount = n - primeCount`.
- Calculate `factorial(primeCount)` and `factorial(nonPrimeCount)` modulo `10^9 + 7`.
- Return the product of the two factorials modulo `10^9 + 7`.

## Sieve of Eratosthenes
This is the most efficient approach for this problem, especially if `n` were larger. It uses the Sieve of Eratosthenes algorithm to find all prime numbers up to `n` in a highly optimized manner before proceeding with the factorial calculations.
**Time:** O(n * log(log(n))). The Sieve algorithm is the dominant part. The subsequent counting and factorial calculations take O(n), which is less significant. · **Space:** O(n). We need a boolean array of size `n+1` for the sieve.
**Pros:** The most time-efficient method for finding all primes in a given range.; Optimal for problems where prime numbers in a range need to be identified multiple times or in bulk.
**Cons:** Uses extra space proportional to `n` for the sieve array.; Slightly more complex to implement than trial division methods.
### Explanation
The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a specified integer. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2.

The algorithm proceeds as follows:
1. Create a boolean array `isPrime` of size `n+1` and initialize all entries to `true`. A value `isPrime[i]` will be `false` if `i` is not a prime, `true` otherwise. Mark `isPrime[0]` and `isPrime[1]` as `false`.
2. Iterate from `p = 2` up to `sqrt(n)`.
3. If `isPrime[p]` is `true` (meaning `p` is a prime), then iterate through all multiples of `p` (starting from `p*p`) and mark them as `false`.

After the sieve has run, we can count the number of primes (`primeCount`) by simply iterating through the `isPrime` array from 2 to `n` and counting the `true` values. Once `primeCount` is known, the rest of the logic is the same: calculate `(primeCount!) * ((n - primeCount)!)` modulo `10^9 + 7`.

```java
class Solution {
    public int numPrimeArrangements(int n) {
        long MOD = 1_000_000_007;
        
        // Step 1: Find prime count using Sieve of Eratosthenes
        boolean[] isPrime = new boolean[n + 1];
        java.util.Arrays.fill(isPrime, true);
        if (n >= 0) isPrime[0] = false;
        if (n >= 1) isPrime[1] = false;

        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        int primeCount = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primeCount++;
            }
        }

        // Step 2: Calculate factorials
        int nonPrimeCount = n - primeCount;
        long ans = factorial(primeCount, MOD);
        ans = (ans * factorial(nonPrimeCount, MOD)) % MOD;
        
        return (int) ans;
    }

    private long factorial(int k, long MOD) {
        long res = 1;
        for (int i = 2; i <= k; i++) {
            res = (res * i) % MOD;
        }
        return res;
    }
}
```
### Algorithm
- Create a boolean array `isPrime` of size `n+1` and initialize it to `true`.
- Run the Sieve of Eratosthenes algorithm on this array to mark all non-prime numbers up to `n`.
- Count the number of `true` values in `isPrime` from index 2 to `n` to get `primeCount`.
- Calculate `nonPrimeCount = n - primeCount`.
- Calculate `factorial(primeCount)` and `factorial(nonPrimeCount)` modulo `10^9 + 7`.
- Return the product of the two factorials modulo `10^9 + 7`.

# Solutions
### Java

```java
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int numPrimeArrangements ( int n ) { int cnt = count ( n ); long ans = f ( cnt ) * f ( n - cnt ); return ( int ) ( ans % MOD ); } private long f ( int n ) { long ans = 1 ; for ( int i = 2 ; i <= n ; ++ i ) { ans = ( ans * i ) % MOD ; } return ans ; } private int count ( int n ) { int cnt = 0 ; boolean [] primes = new boolean [ n + 1 ]; Arrays . fill ( primes , true ); for ( int i = 2 ; i <= n ; ++ i ) { if ( primes [ i ]) { ++ cnt ; for ( int j = i + i ; j <= n ; j += i ) { primes [ j ] = false ; } } } return cnt ; } }
```

### CPP

```cpp
using ll = long long ; const int MOD = 1e9 + 7 ; class Solution { public: int numPrimeArrangements ( int n ) { int cnt = count ( n ); ll ans = f ( cnt ) * f ( n - cnt ); return ( int ) ( ans % MOD ); } ll f ( int n ) { ll ans = 1 ; for ( int i = 2 ; i <= n ; ++ i ) ans = ( ans * i ) % MOD ; return ans ; } int count ( int n ) { vector < bool > primes ( n + 1 , true ); int cnt = 0 ; for ( int i = 2 ; i <= n ; ++ i ) { if ( primes [ i ]) { ++ cnt ; for ( int j = i + i ; j <= n ; j += i ) primes [ j ] = false ; } } return cnt ; } };
```

### Python

```python
class Solution : def numPrimeArrangements ( self , n : int ) -> int : def count ( n ): cnt = 0 primes = [ True ] * ( n + 1 ) for i in range ( 2 , n + 1 ): if primes [ i ]: cnt += 1 for j in range ( i + i , n + 1 , i ): primes [ j ] = False return cnt cnt = count ( n ) ans = factorial ( cnt ) * factorial ( n - cnt ) return ans % ( 10 ** 9 + 7 )
```