Prime Arrangements
给一个数字n, 求1到n中的排列, 要求prime位上的数要是prime. 通过观察可以看到, 1到n除了prime就是非prime, 所以找到prime后, 求可以知道答案了. 这里取模的时候注意要每次乘法都取, 不然太大.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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; } } |