题解的核心思想是将1到n的数字分为质数和非质数两部分,然后分别在质数的索引位置放置所有质数,非质数索引位置放置所有非质数。首先,算法通过遍历从2到n的所有数字,使用试除法判断每个数是否为质数。如果一个数是质数,质数计数器p递增;如果不是,非质数计数器c递增。之后,为了计算所有可能的排列方案,算法计算p个质数可以有多少种排列方式,即计算p的阶乘。同理,也计算非质数的c个数字的阶乘。最后,将这两个阶乘相乘得到总排列数,由于结果可能非常大,最后结果对10^9 + 7取模。
时间复杂度: O(n√n)
空间复杂度: O(1)
class Solution:
def numPrimeArrangements(self, n: int) -> int:
p = 0 # 计数质数的数量
c = 1 # 计数非质数的数量,从1开始因为1不是质数
for i in range(2, n+1):
for j in range(2, int(i**0.5)+1):
if i % j == 0:
c += 1 # 如果i不是质数,增加非质数计数
p -= 1 # 修正之前错误的质数计数增加
break
p += 1 # 增加质数计数
print(p, c) # 输出质数和非质数的数量
r = 1 # 用于计算结果的变量
for i in range(2, p+1):
r *= i # 计算质数的排列数
for i in range(2, c+1):
r *= i # 计算非质数的排列数
return r % 1_000_000_007 # 返回结果对10^9 + 7取模的值