Prime arrangements

Math

60.8% acceptance

Feb 25, 2026

444

538

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.) (Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.) Since the answer may be large, return the answer modulo 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_prime_arrangements(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    // Count primes up to n using sieve
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    if n >= 1 { is_prime[1] = false; }
    let mut i = 2;
    while i * i <= n {
      if is_prime[i] {
        let mut j = i * i;
        while j <= n {
          is_prime[j] = false;
          j += i;
        }
      }
      i += 1;
    }
    let prime_count = is_prime.iter().filter(|&&b| b).count() as i64;
    let non_prime_count = n as i64 - prime_count;
    // factorial of prime_count * factorial of non_prime_count mod MOD
    let fact = |x: i64| -> i64 {
      let mut res = 1i64;
      for i in 2..=x {
        res = res * i % MOD;
      }
      res
    };
    ((fact(prime_count) * fact(non_prime_count)) % MOD) as i32
  }
}