09 Sept 2026•Easy•Go / Python / TypeScript

Prime Arrangements

Count permutations where prime values occupy exactly the prime-numbered positions.

Count primes through n with a sieve, then multiply the factorials of the prime and non-prime counts modulo one billion seven.

Complexity

O(n log log n) time and O(n) sieve space.

Solution files

Go•prime-arrangements/solution.go

package main

func numPrimeArrangements(n int) int {
	prime := make([]bool, n+1)
	for index := 2; index <= n; index++ {
		prime[index] = true
	}
	for value := 2; value*value <= n; value++ {
		if prime[value] {
			for multiple := value * value; multiple <= n; multiple += value {
				prime[multiple] = false
			}
		}
	}
	count := 0
	for _, value := range prime {
		if value {
			count++
		}
	}
	const modulo = 1000000007
	factorial := func(value int) int {
		result := 1
		for factor := 2; factor <= value; factor++ {
			result = result * factor % modulo
		}
		return result
	}
	return factorial(count) * factorial(n-count) % modulo
}

Python•prime-arrangements/solution.py

class Solution:
    def numPrimeArrangements(self, n: int) -> int:
        prime = [True] * (n + 1); prime[0] = False
        if n >= 1: prime[1] = False
        for value in range(2, int(n ** 0.5) + 1):
            if prime[value]:
                for multiple in range(value * value, n + 1, value): prime[multiple] = False
        count = sum(prime); modulo = 1_000_000_007
        def factorial(value: int) -> int:
            result = 1
            for factor in range(2, value + 1): result = result * factor % modulo
            return result
        return factorial(count) * factorial(n - count) % modulo

TypeScript•prime-arrangements/solution.ts

function numPrimeArrangements(n: number): number {
  const prime = new Array<boolean>(n + 1).fill(true); if (n >= 0) prime[0] = false; if (n >= 1) prime[1] = false;
  for (let value = 2; value * value <= n; value += 1) if (prime[value]) for (let multiple = value * value; multiple <= n; multiple += value) prime[multiple] = false;
  const primeCount = prime.filter(Boolean).length; const modulo = 1_000_000_007;
  const factorial = (value: number): number => { let result = 1; for (let factor = 2; factor <= value; factor += 1) result = (result * factor) % modulo; return result; };
  return Number(
    (BigInt(factorial(primeCount)) * BigInt(factorial(n - primeCount))) % BigInt(modulo),
  );
}