标签: 数学
难度: Easy
请你帮忙给从 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 <= n <= 100运行时间: 24 ms
内存: 16.0 MB
class Solution:
def numPrimeArrangements(self, n: int) -> int:
p = 0
c = 1
for i in range(2, n+1):
for j in range(2, int(i**0.5)+1):
if i%j == 0:
c += 1
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
题解的核心思想是将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取模的值
在判断一个数是否为质数的循环中，如果在内层循环中发现某个数i可以被j整除（即`i % j == 0`），就会立即执行`break`语句。这个`break`语句会中断内层循环，从而不会继续检查更大的j值是否也能整除i。这确保了一旦找到第一个能使i整除的j，就停止进一步的检查，从而提高效率并减少不必要的计算。
在题解中，`p -= 1`的操作出现是因为算法的设计错误。原本意图是在每次循环开始前默认将当前数i认为是质数，然后通过循环检验其是否真的是质数。如果发现i能被某个j整除，则应该将其视为非质数，并修正之前错误增加的质数计数。然而，这种实现方法容易引起混淆，并且增加了错误的机率，不是一种推荐的做法。更好的实现是只在确认i为质数后再将质数计数器p增加。
在直接的连乘计算阶乘时，确实存在整数溢出的风险，尤其是当n较大时。为了避免整数溢出，可以在每次乘法操作后立即对结果进行模运算（模一个大素数，如10^9+7）。这样可以确保结果始终在整数表示范围内，防止溢出。此外，使用模运算还可以保证最终结果的正确性，因为乘法运算在模运算下是封闭的。
在最终求解时，为了处理阶乘结果可能非常大的情况，确实在每次乘法操作后就进行了模运算。通过将中间结果每次乘法后都对10^9+7取模，不仅可以防止溢出，还可以保证整个运算过程中数据的大小被有效控制。这是处理大数运算常用的技术，特别是在组合数学和数论中频繁使用。