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;
}
}