LeetCode 1175. 质数排列（质数判断+组合数学）

---

0 题目

• LeetCode 1175. 质数排列

1 解题思路

1.1 质数判断+组合数学

$$\begin{gathered} 本题总的方案数=「所有质数都放在质数索引上的方案数」\times \\ 「所有合数都放在合数索引上的方案数」 \end{gathered}$$

「所有质数都放在质数索引上的方案数」:

• 首先求出$[1,n]$范围内所有质数的个数$primeNum$
  • 枚举100以内所有质数+二分
  • 试除法
• 再求出质数个数 $\text{primeNum}$ 的阶乘即为方案数

「所有合数都放在合数索引上的方案数」：

• $n-primeNum$即为所有合数的个数，再求其阶乘即为方案数

排列：
$$A(m,n)=\frac{n!}{(n-m)!}$$

组合：
$$C(m,n)=\frac{n!}{m!\times (n-m)!}$$

1.1.1 代码实现

1.1.1.1 枚举100以内所有质数+二分

class Solution {
    
    // 枚举100以内所有质数
    private static int[] PRIME = {
    2, 3, 5, 7,
                                11, 13, 17, 19,
                                23, 29,
                                31, 37,
                                41, 43, 47,
                                53, 59,
                                61, 67,
                                71, 73, 79,
                                83, 89,
                                97};
    private static final int MOD =  1000000007;
    public int numPrimeArrangements(int n) {
    
        // 利用二分求取质数个数
        int primeNum = binarySearch(n) + 1;
        // 利用阶乘求方案数
        return (int) (calcFactorial(primeNum) * calcFactorial(n - primeNum) % MOD) ;
    }

    private long calcFactorial(int m) {
    
        long res = 1;
        while (m != 0) {
    
            res *= m;
            res %= MOD;
            m--;
        }
        return res;
    }

    private int binarySearch(int n) {
    
        int left = 0, right = PRIME.length - 1;
        while (left < right) {
    
            int mid = left + (right - left + 1) / 2;
            if (PRIME[mid] > n) {
    
                right = mid - 1;
            } else {
    
                left = mid;
            }
        }
        return left;
    }
}

1.1.1.2 试除法

class Solution {
    
    private static final int MOD = 1000000007;

    public int numPrimeArrangements(int n) {
    
        // 试除法求取质数个数
        int primeNum = 0;
        for (int i = 1; i <= n; i++) {
    
            if (isPrime(i)) {
    
                primeNum++;
            }
        }
        // 利用阶乘求方案数
        return (int) (calcFactorial(primeNum) * calcFactorial(n - primeNum) % MOD);
    }

    public boolean isPrime(int n) {
    
        if (n == 1) {
    
            return false;
        }
        for (int i = 2; i * i <= n; i++) {
    
            if (n % i == 0) {
    
                return false;
            }
        }
        return true;
    }

    public long calcFactorial(int n) {
    
        long res = 1;
        for (int i = 1; i <= n; i++) {
    
            res *= i;
            res %= MOD;
        }
        return res;
    }
}

2 Reference

• 质数排列