Prime Arrangements: Counting Permutations of Primes and Composites

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

This is LeetCode 1175: Prime Arrangements. A few examples:

• n = 5 returns 12 (3 primes at 3 prime indices, 2 non-primes at 2 non-prime indices: 3! * 2! = 12)
• n = 100 returns 682289015
• n = 1 returns 1 (no primes, only one arrangement)

The constraint is 1 <= n <= 100, so the solution does not need to handle enormous inputs. But the modular arithmetic still matters because factorials grow fast.

The approach

Think about what the problem is really asking. You have positions 1 through n, and you need to place numbers 1 through n into those positions. The rule: every prime number must land on a prime-indexed position, and every non-prime number must land on a non-prime-indexed position.

Since primes and non-primes occupy completely separate slots, the two groups are independent. You can arrange the primes among prime positions in any order, and separately arrange the non-primes among non-prime positions in any order. The total count is just the product of the two groups' arrangement counts.

How many ways can you arrange k items into k slots? That is k! (k factorial). So the answer is:

factorial(primeCount) * factorial(n - primeCount) mod (10^9 + 7)

The entire problem reduces to one subproblem: count how many primes exist in the range [1, n]. Once you have that, a couple of factorial computations finish the job.

Counting primes up to n

A number k is prime if it is greater than 1 and has no divisors other than 1 and itself. For small k, you can check this by testing divisors from 2 up to the square root of k. If none divide evenly, the number is prime.

This is the same logic from the Sieve of Eratosthenes, but since n is at most 100, a simple loop works fine.

Python solution

def numPrimeArrangements(n):
    MOD = 10**9 + 7

    def is_prime(k):
        if k < 2:
            return False
        for d in range(2, int(k**0.5) + 1):
            if k % d == 0:
                return False
        return True

    prime_count = sum(1 for i in range(1, n + 1) if is_prime(i))
    non_prime_count = n - prime_count

    result = 1
    for i in range(1, prime_count + 1):
        result = result * i % MOD
    for i in range(1, non_prime_count + 1):
        result = result * i % MOD

    return result

Walkthrough

Let's trace through numPrimeArrangements(10) step by step.

The key observation is that we never build any permutations. We just count primes, compute two factorials, and multiply. The combinatorics do all the heavy lifting.

Complexity analysis

The prime-counting loop runs n iterations. Each primality check takes O(sqrt(n)) in the worst case. The factorial computations are O(n) combined. No extra data structures are needed beyond a few variables.

For n up to 100, both approaches finish instantly, but the factorial approach scales gracefully while brute force does not.

The building blocks

This problem is built on two reusable patterns:

Prime counting. You need to identify which numbers in a range are prime. Whether you use trial division or a sieve depends on the range size. For n up to 100, trial division is the right call. For n up to 10^6 or beyond, the Sieve of Eratosthenes becomes essential. Recognizing when you need a prime count is the first step in many number theory problems.

Factorial as a counting tool. The number of ways to arrange k distinct items into k distinct slots is k!. This is the fundamental counting principle in action: the first slot has k choices, the second has k - 1, and so on. Whenever a problem asks "how many permutations satisfy some constraint," check whether the constraint splits items into independent groups. If it does, the answer is a product of factorials.

Edge cases to watch for

Before submitting, make sure your solution handles these:

• n = 1: The only number is 1, which is not prime. There are 0 primes and 1 non-prime. 0! * 1! = 1 * 1 = 1.
• n = 2: Primes: . Non-primes: . 1! * 1! = 1.
• n = 3: Primes: . Non-primes: . 2! * 1! = 2.
• n = 100: The answer is 682289015. Make sure you apply the modulo at each multiplication step, not just at the end, to avoid integer overflow in languages with fixed-width integers.
• 1 is not prime: This trips people up. 1 has only one divisor (itself), so it fails the "exactly two distinct divisors" definition of a prime.

From understanding to recall

You have seen that the problem boils down to counting primes and multiplying factorials. The logic is clean: split positions into prime and non-prime, count each group, compute factorials, multiply.

But knowing the approach and producing it under pressure are different things. The connection you need to internalize is: "independent groups of items filling independent groups of slots" maps to "product of factorials." That pattern appears in many counting problems, and the only way to make it automatic is repeated practice.

Spaced repetition helps here. Solve this problem from scratch today, then revisit it in a few days. Each time, you rebuild the prime-counting step and the factorial multiplication from memory. After a few rounds, the pattern is second nature.

Related posts

• Count Primes - The classic prime-counting problem using the Sieve of Eratosthenes, which gives you the primeCount this problem needs
• Factorial Trailing Zeroes - Another problem where reasoning about factorial properties avoids computing the factorial itself
• Combinations - A backtracking problem where counting arrangements (C(n, k)) is the core idea, connecting to the factorial-based counting used here