[1175. prime number arrangement]

source ： Power button （LeetCode）

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

Method ： Prime number judgment + Combinatorial mathematics

Ideas

Find the number of schemes that meet the conditions , So that all prime numbers are placed on the prime index , All composite numbers are placed on the composite index , Prime number placement and composite number placement are independent of each other , The total number of schemes is 「 The number of schemes in which all prime numbers are placed on the prime index 」 ×「 The number of schemes in which all composite numbers are placed on the composite index 」. seek 「 The number of schemes in which all prime numbers are placed on the prime index 」, That is, find the number of prime numbers numPrimes The factorial .「 The number of schemes in which all composite numbers are placed on the composite index 」 Empathy . When finding the number of primes , You can use trial division .

Code ：

const int MOD = 1e9 + 7;

class Solution {
    
public:
    int numPrimeArrangements(int n) {
    
        int numPrimes = 0;
        for (int i = 1; i <= n; i++) {
    
            if (isPrime(i)) {
    
                numPrimes++;
            }
        }
        return (int) (factorial(numPrimes) * factorial(n - numPrimes) % MOD);
    }

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

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

Execution time ：0 ms, In all C++ Defeated in submission 100.00% Users of
Memory consumption ：5.9 MB, In all C++ Defeated in submission 45.81% Users of
author：LeetCode-Solution