Prime Arrangements

给一个数字n, 求1到n中的排列, 要求prime位上的数要是prime. 通过观察可以看到, 1到n除了prime就是非prime, 所以找到prime后, 求可以知道答案了. 这里取模的时候注意要每次乘法都取, 不然太大.

class Solution {
    public int numPrimeArrangements(int n) {
        int p = 0;
        for(int i = 1; i <= n; i++) {
            if(isPrime(i))
                p++;
        }
        int np = n - p;
        long res = 1;
        for(int i = p; i > 0; i--)
            res = (res * i) % 1000000007;
        for(int i = np; i > 0; i--)
            res = (res * i) % 1000000007;
        return (int)res;
    }
    
    private boolean isPrime(int n) {
        if(n <= 1)
            return false;
        for(int i = 2; i <= Math.sqrt(n); i++) {
            if(n % i == 0)
                return false;
        }
        return true;
    }
}