09 Sept 2026•Go / Python / TypeScript•Easy

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
Python prime-arrangements/solution.py
TypeScript prime-arrangements/solution.ts

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 + class="syntax-number">1); prime[class="syntax-number">0] = False
        if n >= class="syntax-number">1: prime[class="syntax-number">1] = False
        for value in range(class="syntax-number">2, int(n ** class="syntax-number">0.5) + class="syntax-number">1):
            if prime[value]:
                for multiple in range(value * value, n + class="syntax-number">1, value): prime[multiple] = False
        count = sum(prime); modulo = 1_000_000_007
        def factorial(value: int) -> int:
            result = class="syntax-number">1
            for factor in range(class="syntax-number">2, value + class="syntax-number">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 + class="syntax-number">1).fill(true); if (n >= class="syntax-number">0) prime[class="syntax-number">0] = false; if (n >= class="syntax-number">1) prime[class="syntax-number">1] = false;
  for (let value = class="syntax-number">2; value * value <= n; value += class="syntax-number">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 = class="syntax-number">1; for (let factor = class="syntax-number">2; factor <= value; factor += class="syntax-number">1) result = (result * factor) % modulo; return result; };
  return Number(
    (BigInt(factorial(primeCount)) * BigInt(factorial(n - primeCount))) % BigInt(modulo),
  );
}