Prime Arrangements — Easy Problem & Solution

Problem statement

Count the permutations of the numbers 1 to n in which every prime number sits at a prime position (positions are numbered from 1).

A prime is an integer greater than 1 whose only positive divisors are 1 and itself.

The count can be huge, so return it modulo 10^9 + 7.

Example 1

Input: n = 5
Output: 12
Explanation: The primes 2, 3, 5 must fill positions 2, 3, 5 (3! ways) and 1, 4 fill positions 1, 4 (2! ways): 6 × 2 = 12. For example [1,2,5,4,3] is valid, [5,2,3,4,1] is not (5 sits at position 1).

Example 2

Input: n = 100
Output: 682289015

Example 3

Input: n = 1
Output: 1

Constraints

• 1 <= n <= 100

How to solve Prime Arrangements

Primes and prime positions are equinumerous, so a valid permutation is a permutation of the primes among the prime positions times a permutation of the rest: p! · (n − p)!.

Approach

1. Count the primes p in [1, n] (trial division or a sieve).
2. Multiply 1 · 2 · … · p and 1 · 2 · … · (n − p) together, reducing modulo 10^9 + 7 after each multiplication.
3. Return the product.

Why it works

The p prime values must go to prime positions, and there are exactly p prime positions in 1..n, so the primes fill them exactly and the n − p other values fill the other positions. Any arrangement of each group works, and the choices are independent, so the count is the product of the two factorials.

Complexity

• Time — O(n √n) for the prime count (O(n log log n) with a sieve)
• Space — O(1)

Pitfalls

• 1 is not prime, so position 1 is a non-prime position.
• Reduce after every multiplication: 25! already overflows 64 bits.
• In 32-bit arithmetic product * i overflows before the modulo — use a 64-bit accumulator.

Reference solution

Python

def numPrimeArrangements(n: int) -> int:
    MOD = 10 ** 9 + 7
    primes = 0
    for x in range(2, n + 1):
        d = 2
        while d * d <= x and x % d != 0:
            d += 1
        if d * d > x:
            primes += 1
    result = 1
    for i in range(2, primes + 1):
        result = result * i % MOD
    for i in range(2, n - primes + 1):
        result = result * i % MOD
    return result

JavaScript

var numPrimeArrangements = function(n) {
    var MOD = 1000000007;
    var primes = 0;
    for (var x = 2; x <= n; x++) {
        var d = 2;
        while (d * d <= x && x % d !== 0) d++;
        if (d * d > x) primes++;
    }
    var result = 1;
    for (var i = 2; i <= primes; i++) result = (result * i) % MOD;
    for (var j = 2; j <= n - primes; j++) result = (result * j) % MOD;
    return result;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find Nth Root of M Easy
• Valid Boomerang Easy
• Surface Area of 3D Shapes Easy
• Rectangle Overlap Easy
• Day of the Week Easy
• Number of Days Between Two Dates Easy