题目描述
请你帮忙给从 1 到 n
的数设计排列方案,使得所有的质数都应该被放在 质数索引(索引从 1 开始)上;你需要返回可能的方案总数。
(让我们一起来回顾一下“质数”:质数一定是大于 1 的,并且不能用两个小于它的正整数的乘积来表示。)
由于答案可能会很大,返回答案 模 10^9 + 7
之后的结果。
样例
输入:n = 5
输出:12
解释:举个例子,[1,2,5,4,3] 是一个有效的排列,
但 [5,2,3,4,1] 不是,因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
输入:n = 100
输出:682289015
限制
1 <= n <= 100
算法
(排列) $O(n \sqrt{n})$
- 将数字分为质数和非质数两部分。
- 假设有 $p$ 个质数,答案就是 $p! \cdot (n - p)!$。
时间复杂度
- 需要求质数的个数,暴力的做法需要 $O(n \sqrt{n})$ 的时间,可以采用线性筛法在 $O(n)$ 的时间内求出。
空间复杂度
- 暴力仅需要常数空间,线性筛法需要 $O(n)$ 的空间。
C++ 代码
class Solution {
public:
const int mod = 1000000007;
bool isPrime(int x) {
if (x <= 1)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
long long factorial(int x) {
long long tot = 1;
for (int i = 2; i <= x; i++)
tot = tot * i % mod;
return tot;
}
int numPrimeArrangements(int n) {
int p = 0;
for (int i = 1; i <= n; i++)
if (isPrime(i))
p++;
return factorial(p) * factorial(n - p) % mod;
}
};