LeetCode 1175. Prime number arrangement (prime number judgment + Combinatorial Mathematics)

---

0 subject

• LeetCode 1175. Permutation of prime numbers

1 Their thinking

1.1 Prime number judgment + Combinatorial mathematics

$$\begin{gathered} BentopictotalOfFangcaseCount=「theYesqualityCountalldischargestayqualityCountCableleadOnOfFangcaseCount」\times \\ 「theYescloseCountalldischargestaycloseCountCableleadOnOfFangcaseCount」 \end{gathered}$$

「 The number of schemes in which all prime numbers are placed on the prime index 」:

• First of all find out $[1,n]$ The number of all prime numbers in the range $primeNum$
  • enumeration 100 All prime numbers within + Two points
  • Trial division
• Then find the number of prime numbers $\text{primeNum}$ Of Factorial is the number of schemes

「 The number of schemes in which all composite numbers are placed on the composite index 」：

• $n-primeNum$ That is, the number of all composite numbers , Then the factorial is the number of schemes

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

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

1.1.1 Code implementation

1.1.1.1 enumeration 100 All prime numbers within + Two points

class Solution {
    
    //  enumeration 100 All prime numbers within 
    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) {
    
        //  Use bisection to find the number of prime numbers 
        int primeNum = binarySearch(n) + 1;
        //  Use factorial to find the number of schemes 
        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 Trial division

class Solution {
    
    private static final int MOD = 1000000007;

    public int numPrimeArrangements(int n) {
    
        //  Try division to get the number of prime numbers 
        int primeNum = 0;
        for (int i = 1; i <= n; i++) {
    
            if (isPrime(i)) {
    
                primeNum++;
            }
        }
        //  Use factorial to find the number of schemes 
        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

• Permutation of prime numbers