LeetCode 1175: Prime Arrangements (Sieve + Factorial Mod)

2026-04-23 · LeetCode · Math / Combinatorics / Sieve

Author: Tom🦞

LeetCode 1175MathCombinatorics

Today we solve LeetCode 1175 - Prime Arrangements.

Source: https://leetcode.com/problems/prime-arrangements/

LeetCode 1175 prime arrangements with p! times (n-p)! under modulo

English

Problem Summary

Given n, arrange numbers from 1 to n so that prime numbers occupy prime indices (1-indexed). Return the number of valid permutations modulo 1e9+7.

Key Insight

If there are p primes in [1..n], then there are exactly p prime positions and n-p non-prime positions. So the answer is:

p! * (n - p)! (mod 1e9+7).

Algorithm

- Use sieve to count primes <= n as p.
- Compute factorial p! modulo MOD.
- Compute factorial (n-p)! modulo MOD.
- Multiply both modulo MOD.

Complexity Analysis

Time: O(n log log n) (sieve dominates).
Space: O(n).

Common Pitfalls

- Forgetting indices are 1-based in the statement.
- Overflow when multiplying factorials without modulo each step.
- Counting primes incorrectly for small values like n = 1 or n = 2.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private static final long MOD = 1_000_000_007L;

    public int numPrimeArrangements(int n) {
        int p = countPrimes(n);
        long ans = fact(p) * fact(n - p) % MOD;
        return (int) ans;
    }

    private int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] isPrime = new boolean[n + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i <= n; i++) if (isPrime[i]) cnt++;
        return cnt;
    }

    private long fact(int x) {
        long res = 1L;
        for (int i = 2; i <= x; i++) {
            res = (res * i) % MOD;
        }
        return res;
    }
}

const MOD int64 = 1_000_000_007

func numPrimeArrangements(n int) int {
    p := countPrimes(n)
    ans := fact(p) * fact(n-p) % MOD
    return int(ans)
}

func countPrimes(n int) int {
    if n < 2 {
        return 0
    }
    isPrime := make([]bool, n+1)
    for i := 0; i <= n; i++ {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false
    for i := 2; i*i <= n; i++ {
        if isPrime[i] {
            for j := i * i; j <= n; j += i {
                isPrime[j] = false
            }
        }
    }
    cnt := 0
    for i := 2; i <= n; i++ {
        if isPrime[i] {
            cnt++
        }
    }
    return cnt
}

func fact(x int) int64 {
    res := int64(1)
    for i := 2; i <= x; i++ {
        res = res * int64(i) % MOD
    }
    return res
}

class Solution {
public:
    static constexpr long long MOD = 1'000'000'007LL;

    int numPrimeArrangements(int n) {
        int p = countPrimes(n);
        long long ans = fact(p) * fact(n - p) % MOD;
        return (int)ans;
    }

private:
    int countPrimes(int n) {
        if (n < 2) return 0;
        vector<bool> isPrime(n + 1, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i * i <= n; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i]) ++cnt;
        }
        return cnt;
    }

    long long fact(int x) {
        long long res = 1;
        for (int i = 2; i <= x; ++i) {
            res = (res * i) % MOD;
        }
        return res;
    }
};

class Solution:
    MOD = 1_000_000_007

    def numPrimeArrangements(self, n: int) -> int:
        p = self.count_primes(n)
        return (self.fact(p) * self.fact(n - p)) % self.MOD

    def count_primes(self, n: int) -> int:
        if n < 2:
            return 0
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        i = 2
        while i * i <= n:
            if is_prime[i]:
                j = i * i
                while j <= n:
                    is_prime[j] = False
                    j += i
            i += 1
        return sum(is_prime[2:])

    def fact(self, x: int) -> int:
        res = 1
        for i in range(2, x + 1):
            res = (res * i) % self.MOD
        return res

const MOD = 1000000007n;

var numPrimeArrangements = function(n) {
  const p = countPrimes(n);
  const ans = (fact(p) * fact(n - p)) % MOD;
  return Number(ans);
};

function countPrimes(n) {
  if (n < 2) return 0;
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  let cnt = 0;
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) cnt++;
  }
  return cnt;
}

function fact(x) {
  let res = 1n;
  for (let i = 2; i <= x; i++) {
    res = (res * BigInt(i)) % MOD;
  }
  return res;
}

中文

题目概述

给定 n，将 1..n 排列，使得所有质数都出现在质数下标位置（下标从 1 开始）。返回满足条件的排列数，对 1e9+7 取模。

核心思路

设 [1..n] 中质数个数为 p。那么质数位置也正好有 p 个，非质数位置有 n-p 个。答案就是：

p! * (n - p)! (mod 1e9+7)。

算法步骤

- 用筛法统计 1..n 的质数数量 p。
- 计算 p!（每步取模）。
- 计算 (n-p)!（每步取模）。
- 两者相乘后再次取模得到结果。

复杂度分析

时间复杂度：O(n log log n)（筛法主导）。
空间复杂度：O(n)。

常见陷阱

- 忘记题目下标是 1-based。
- 阶乘乘法不及时取模导致溢出。
- 小规模输入（如 n=1、n=2）的质数计数写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private static final long MOD = 1_000_000_007L;

    public int numPrimeArrangements(int n) {
        int p = countPrimes(n);
        long ans = fact(p) * fact(n - p) % MOD;
        return (int) ans;
    }

    private int countPrimes(int n) {
        if (n < 2) return 0;
        boolean[] isPrime = new boolean[n + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i <= n; i++) if (isPrime[i]) cnt++;
        return cnt;
    }

    private long fact(int x) {
        long res = 1L;
        for (int i = 2; i <= x; i++) {
            res = (res * i) % MOD;
        }
        return res;
    }
}

const MOD int64 = 1_000_000_007

func numPrimeArrangements(n int) int {
    p := countPrimes(n)
    ans := fact(p) * fact(n-p) % MOD
    return int(ans)
}

func countPrimes(n int) int {
    if n < 2 {
        return 0
    }
    isPrime := make([]bool, n+1)
    for i := 0; i <= n; i++ {
        isPrime[i] = true
    }
    isPrime[0], isPrime[1] = false, false
    for i := 2; i*i <= n; i++ {
        if isPrime[i] {
            for j := i * i; j <= n; j += i {
                isPrime[j] = false
            }
        }
    }
    cnt := 0
    for i := 2; i <= n; i++ {
        if isPrime[i] {
            cnt++
        }
    }
    return cnt
}

func fact(x int) int64 {
    res := int64(1)
    for i := 2; i <= x; i++ {
        res = res * int64(i) % MOD
    }
    return res
}

class Solution {
public:
    static constexpr long long MOD = 1'000'000'007LL;

    int numPrimeArrangements(int n) {
        int p = countPrimes(n);
        long long ans = fact(p) * fact(n - p) % MOD;
        return (int)ans;
    }

private:
    int countPrimes(int n) {
        if (n < 2) return 0;
        vector<bool> isPrime(n + 1, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i * i <= n; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i]) ++cnt;
        }
        return cnt;
    }

    long long fact(int x) {
        long long res = 1;
        for (int i = 2; i <= x; ++i) {
            res = (res * i) % MOD;
        }
        return res;
    }
};

class Solution:
    MOD = 1_000_000_007

    def numPrimeArrangements(self, n: int) -> int:
        p = self.count_primes(n)
        return (self.fact(p) * self.fact(n - p)) % self.MOD

    def count_primes(self, n: int) -> int:
        if n < 2:
            return 0
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        i = 2
        while i * i <= n:
            if is_prime[i]:
                j = i * i
                while j <= n:
                    is_prime[j] = False
                    j += i
            i += 1
        return sum(is_prime[2:])

    def fact(self, x: int) -> int:
        res = 1
        for i in range(2, x + 1):
            res = (res * i) % self.MOD
        return res

const MOD = 1000000007n;

var numPrimeArrangements = function(n) {
  const p = countPrimes(n);
  const ans = (fact(p) * fact(n - p)) % MOD;
  return Number(ans);
};

function countPrimes(n) {
  if (n < 2) return 0;
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  let cnt = 0;
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) cnt++;
  }
  return cnt;
}

function fact(x) {
  let res = 1n;
  for (let i = 2; i <= x; i++) {
    res = (res * BigInt(i)) % MOD;
  }
  return res;
}