1175. prime permutation

Original link ：1175. Permutation of prime numbers

 

solution:

        Calculate the number of prime and non prime numbers , Then calculate the number of methods by permutation and combination

const int mod = 1e9 + 7;
class Solution {
public:
    int numPrimeArrangements(int n) {
        int cnt_p = 0,cnt_o = 0;    // Save the number of prime and non prime numbers 
        for(int i = 2;i <= n;i++) {
            if(isprime(i)) cnt_p++;
        }
        cnt_o = n - cnt_p;

        long long res = 1;    // Return value 
        for(int i = 1;i <= cnt_p;i++)
            res = res * i % mod;
        for(int i = 1;i <= cnt_o;i++)
            res = res * i % mod;
        return (int)res;
    }


    // To judge whether a number is a prime number 
    bool isprime(int x) {
        for(int i = 2;i <= x / i;i++) {
            if(x % i == 0) return false;
        }
        return true;
    }
};