问题描述
请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。
让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1：
输入：n = 5
输出：12
解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
示例 2：
输入：n = 100
输出：682289015
提示：
解题思路
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
27
28
29
30
31
32
33
34
35
36 | class Solution:
def numPrimeArrangements(self, n: int) -> int:
# def num_primes(n: int) -> int:
# is_prime = [True] * (n + 1)
# primes = []
# for i in range(2, n + 1):
# if is_prime[i]:
# primes.append(i)
# for prime in primes:
# x = i * prime
# if x > n:
# break
# is_prime[x] = False
# if i % prime == 0:
# break
# return sum(is_prime[2:])
def num_primes(n: int)->int:
is_prime = [True] * (n + 1)
i = 2
while i * i <= n:
if is_prime[i]:
is_prime[i * i : n + 1 : i] = [False] * len(
range(i * i, n + 1, i)
)
i += 1
return sum(is_prime[2:])
a = num_primes(n)
ans = 1
MOD = 10 ** 9 + 7
for i in range(1, a + 1):
ans = (ans * i) % MOD
for i in range(1, n - a + 1):
ans = (ans * i) % MOD
return ans
|