Daily question -leetcode1175- permutation of prime numbers - Mathematics

Original link

Note：

Prime numbers can be arranged blindly in the position of prime numbers , Non prime numbers can be arranged blindly in the position of non prime numbers , Each is a factorial arrangement

Find out 1 ~ n All prime numbers , Calculate factorials separately , The result multiplied together is the answer

Find the prime number and directly traverse it , Open a table to record whether it is a prime number at present , And how many primes are there to the current position

The code is as follows ：

class Solution {
    
public:
    int mod = 1e9 + 7;

    int numPrimeArrangements(int n) {
    
        vector<int> list;
        int cnt[110];
        for(int i = 2; i <= n; i ++){
    
            bool isPrime = true;
            for(int j = 2; j * j <= i; j ++){
    
                if(i % j == 0)  isPrime = false;
            }
            if(isPrime) list.push_back(i);
            cnt[i] = list.size();
        }

        long long ans = 1, a = cnt[n], b = n - a;
        for(int i = a; i > 1; i --) ans = ans * i % mod;
        for(int i = b; i > 1; i --) ans = ans * i % mod;

        return (int)ans;
        
    }
};