[daily training] 1175 Prime permutation

subject

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

Code

package dayLeetCode;

public class dayleetcode1175 {
    
    int mod = 1000000007;

    //  Find how many prime numbers there are , Then arrange prime numbers and composite numbers 
    public int numPrimeArrangements(int n) {
    
        int numPrimes = 0;
        for (int i = 1; i <= n; i++){
    
            if (isPrime(i)){
    
                numPrimes++;
            }
        }
        return (int)(f(numPrimes) % mod* f(n - numPrimes) % mod) % mod;
    }

    //  Judge whether it is a prime number 
    private boolean isPrime(int k) {
    
        if (k == 1){
    
            return false;
        }
        for (int i = 2; i * i <= k; i++){
    
            if (k % i == 0){
    
                return false;
            }
        }
        return true;
    }
    //  Find the factorial 
    long f(int k){
    
        long ans = 1;
        for (int i = 1; i <= k; i++){
    
            ans *= i;
            ans %= mod;
        }
        return ans;
    }

    public static void main(String[] args) {
    
        dayleetcode1175 obj = new dayleetcode1175();
        System.out.println(obj.numPrimeArrangements(100));
    }
}