Force deduction solution summary 1175 prime number arrangement

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Please help me to 1 To n  Number design arrangement scheme , Make all of 「 Prime number 」 Should be placed in 「 Prime index 」（ Index from 1 Start ） On ; You need to return the total number of possible solutions .

Let's review 「 Prime number 」： The prime number must be greater than 1 Of , And it cannot be expressed by the product of two positive integers less than it .

Because the answer could be big , So please return to the answer model mod 10^9 + 7  Then the result is .

Example 1：

Input ：n = 5
Output ：12
explain ： for instance ,[1,2,5,4,3] Is an effective arrangement , but [5,2,3,4,1] No , Because in the second case, prime numbers 5 It is wrongly placed in the index as 1 Location .
Example 2：

Input ：n = 100
Output ：682289015
 

Tips ：

1 <= n <= 100

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/prime-arrangements
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  Find the quantity of prime and non prime numbers , Then sort them separately . The product is the total number of schemes .

Code ：

public class Solution1175 {

    public int numPrimeArrangements(int n) {
        long primeNum = 0;
        for (long i = 1; i <= n; i++) {
            if (isPrime(i)) {
                primeNum++;
            }
        }
        long result = 1;
        for (long i = 2; i <= primeNum; i++) {
            result = ramainder(result * i, 10_0000_0000 + 7);
        }
        for (long i = 2; i <= (n - primeNum); i++) {
            result = ramainder(result * i, 10_0000_0000 + 7);
        }
        return (int) result;
    }

    private boolean isPrime(long k) {
        if (k < 2) {
            return false;
        }
        for (int i = 2; i < k; i++) {
            if (k % i == 0) {
                return false;
            }
        }
        return true;
    }

    // Modulus operation 
    public static long ramainder(long dividend, long dividor) {
        return dividend % dividor;
    }
}