leetcode-1175-easy
Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)
(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)
Since the answer may be large, return the answer modulo 10^9 + 7.
Example 1:
Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.
Example 2:
Input: n = 100
Output: 682289015
Constraints:
1 <= n <= 100
思路一:分阶段处理,判断数字是否质数,组合公式计算,n 个数字里面有 m 个质数,质数都要放在质数位置,这样有 m!*(n-m)! 种排列方式
public int numPrimeArrangements(int n) {
int primeCount = 0;
for (int i = 1; i <= n; i++) {
if (isPrime(i)) primeCount++;
}
long ans = 1;
for (int i = 1; i <= primeCount; i++) {
ans *= i;
ans %= 1000000007;
}
for (int i = 1; i <= n - primeCount; i++) {
ans *= i;
ans %= 1000000007;
}
return (int)ans;
}
public boolean isPrime(int x) {
if (x == 1 || x % 2 == 0 && x != 2) {
return false;
} else {
for (int i = 2; i < x; i++) {
if (x % i == 0) {
return false;
}
}
}
return true;
}
标签:prime,1175,int,质数,easy,leetcode
From: https://www.cnblogs.com/iyiluo/p/16928252.html