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
这道题说是让返回数字1到n组成的全排列的个数,使得质数都出现在质数的坐标上(坐标从1开始),并且结果对一个很大的数字取余。我们对于质数应该不陌生,小学数学就学过,就是大于1且只能被1和其本身整除的数。刚拿到题时,可能会被这里的全排列,质数坐标啥的所迷惑,并且疑惑地看着其 Easy 的标签,怀疑着人生。但其实这些都是障眼法,完全可以把质数和非质数分离开来,各个排列,比如有 cnt 个质数,那么其排列的方法总数就是 cnt 的阶乘(中学学过),同理,非质数的排列方法就是 n-cnt 的阶乘,然后把二者相乘就行了。所以这道题的难点还是求1到n中所有的质数的个数,这就跟之前那道 Count Primes 一样了。这里可以挨个检查 [1, n] 中的每个数字是否是质数,其实只需要要检测 [3, n] 中的所有奇数,因为除了2以外的质数一定是奇数。判定质数的最简单直接的方法,就是查找看其是否有非1非其本身的因子,这里可以从3开始检测,只需要检测到 sqrt(i) 就行了,而且只用检测奇因子,若是质数,则 cnt 自增1。最后分别计算 cnt 和 n-cnt 的阶乘,并相乘,别忘了对超大数取余,参见代码如下:
解法一:
class Solution {
public:
int numPrimeArrangements(int n) {
long res = 1, cnt = 1, M = 1e9 + 7;
for (int i = 3; i <= n; i += 2) {
bool pass = true;
for (int factor = 3; factor * factor <= i; factor += 2) {
if (i % factor == 0) {
pass = false;
break;
}
}
if (pass) ++cnt;
}
for (int i = 1; i <= cnt; ++i) {
res = res * i % M;
}
for (int i = 1; i <= n - cnt; ++i) {
res = res * i % M;
}
return res;
}
};
其实检测1到n中质数的个数更高效的方法是用 埃拉托斯特尼筛法 Sieve of Eratosthenes,在之前的 Count Primes 中也有讲解到。这里实际上就是快速标记所有不是质数的位置,然后剩下的就都是质数了,对于每个质数,其乘以另一个大于1的数字得到的数字肯定不是质数,只要其小于等于n,就标记为 false。其余部分跟上面的解法没有啥区别,参见代码如下:
解法二:
class Solution {
public:
int numPrimeArrangements(int n) {
long res = 1, cnt = 0, M = 1e9 + 7;
vector<bool> prime(n + 1, true);
prime[0] = false; prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (prime[i]) {
for (int factor = 2; factor * i <= n; ++factor) {
prime[factor * i] = false;
}
}
}
for (int i = 1; i <= n; ++i) {
if (prime[i]) ++cnt;
}
for (int i = 1; i <= cnt; ++i) {
res = res * i % M;
}
for (int i = 1; i <= n - cnt; ++i) {
res = res * i % M;
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1175
类似题目:
参考资料:
https://leetcode.com/problems/prime-arrangements/
https://leetcode.com/problems/prime-arrangements/discuss/371968/Detailed-Explanation-using-Sieve