Prime Arrangements

Prime Arrangements

What is this problem about?

The Prime Arrangements problem asks for the number of permutations of integers 1..n such that prime numbers occupy prime-numbered positions (1-indexed). Return the answer modulo 10^9+7. The key insight: count primes ≤ n, then the answer is primes! × (n-primes)! mod (10^9+7). The math interview pattern is demonstrated.

Why is this asked in interviews?

Amazon asks this easy math problem to test whether candidates can recognize that primes must go in prime positions and composites in composite positions. The count of each group determines the number of independent arrangements.

Algorithmic pattern used

Sieve of Eratosthenes + factorial. Count p = number of primes ≤ n. The prime positions (2,3,5,7,...) must be filled with the p prime numbers — p! ways. The remaining n-p positions must be filled with composites — (n-p)! ways. Answer = p! × (n-p)! mod (10^9+7).

Example explanation

n=5. Primes ≤ 5: {2,3,5}, p=3. Prime positions: {2,3,5}. Composites: {1,4}, (n-p)=2. Answer = 3! × 2! = 6 × 2 = 12.

n=3. Primes: {2,3}, p=2. Non-prime: {1}, (n-p)=1. Answer = 2! × 1! = 2.

Common mistakes candidates make

• Misidentifying 1 as prime (1 is NOT a prime).
• Not applying modulo during factorial computation (overflow).
• Confusing prime positions with prime values (positions 2,3,5,7 are prime positions).
• Not using a sieve (trial division works for small n but demonstrates less mathematical knowledge).

Interview preparation tip

Prime Arrangements rewards mathematical observation over complex algorithms. Always count primes with a Sieve of Eratosthenes for n > 100. The independence of prime-position and composite-position arrangements gives the multiplicative formula p! × (n-p)!. Practice computing factorials modulo a prime — required in all combinatorics problems at competitive levels.