1175. 质数排列

原题链接：1175. 质数排列

 

solution:

        计算出质数和非质数的个数，再通过排列组合计算出方法数

const int mod = 1e9 + 7;
class Solution {
public:
    int numPrimeArrangements(int n) {
        int cnt_p = 0,cnt_o = 0;    //保存质数和非质数的个数
        for(int i = 2;i <= n;i++) {
            if(isprime(i)) cnt_p++;
        }
        cnt_o = n - cnt_p;

        long long res = 1;    //返回值
        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;
    }


    //判断一个数是不是质数
    bool isprime(int x) {
        for(int i = 2;i <= x / i;i++) {
            if(x % i == 0) return false;
        }
        return true;
    }
};