1. 项目概述从一道竞赛题看约数计算的实战策略最近在辅导一些准备参加编程竞赛的同学发现“蓝桥杯”竞赛中一道关于“阶乘约数”的Python题目成了不少人的拦路虎。题目本身并不复杂就是给定一个正整数n要求计算n!n的阶乘的正约数个数。但很多初学者一看到题目第一反应就是先算出n!这个巨大的数然后再去遍历找约数——这个思路在n稍微大一点比如n20的时候程序就会直接卡死或者内存溢出。这其实是一个经典的“算法思维”与“暴力计算”的分水岭问题。它考察的不是你会不会写循环而是你是否理解数论中的核心原理并能够将其转化为高效的代码。今天我就结合自己多年刷题和教学的经验把这个问题的“里子”和“面子”都拆开来讲透让你不仅会做这道题更能掌握一类问题的通用解法。2. 核心思路拆解为什么不能直接计算阶乘2.1 问题本质与暴力法的陷阱我们先来直观感受一下暴力法为什么不可行。n的阶乘n! 1 × 2 × 3 × … × n。当n20时20! 2432902008176640000这已经是一个19位数。如果n100100!是一个158位的天文数字没有任何基本数据类型能直接存储它更别提对它进行遍历求约数了。所以这道题的核心约束就是禁止直接计算并分解大整数n!。我们必须寻找一个不依赖于大数运算的数学方法。2.2 数论基石正约数个数的计算公式解决这个问题的钥匙藏在数论里一个正整数N的正约数个数公式。假设我们将N进行质因数分解得到 N p1^a1 * p2^a2 * ... * pk^ak 其中p1, p2, ..., pk 是不同的质数a1, a2, ..., ak 是对应的指数。 那么N的正约数个数D(N)为 D(N) (a1 1) * (a2 1) * ... * (ak 1)这个公式怎么理解呢我们可以把每个约数想象成从各个质因子的“库存”中挑选数量。对于质因子p1我们可以挑0个、1个、…、a1个共有(a11)种选择。各个质因子的选择是独立的所以总的挑选方式即约数的个数就是每种选择数的乘积。2.3 从N到N!的思路转换现在我们的目标N变成了n!。n! 1×2×3×…×n。根据乘法结合律n!的质因数分解等于从1到n每个数字的质因数分解的“总和”。 举个例子计算10!的约数个数。 10! 10 × 9 × 8 × … × 2 × 1。 我们不需要算出3628800再分解而是可以分别分解每个乘数10 2 × 59 3²8 2³7 76 2 × 35 54 2²3 32 21 1 (忽略)然后我们把所有质因子的指数加起来 质因子2: 来自10(1次)、8(3次)、6(1次)、4(2次)、2(1次)。总计 13121 8次。 质因子3: 来自9(2次)、6(1次)、3(1次)。总计 211 4次。 质因子5: 来自10(1次)、5(1次)。总计 11 2次。 质因子7: 来自7(1次)。总计 1次。所以10! 2^8 × 3^4 × 5^2 × 7^1。 根据约数个数公式10!的约数个数 (81) × (41) × (21) × (11) 9 × 5 × 3 × 2 270。至此我们的算法蓝图就清晰了遍历从2到n的每一个整数i对i进行质因数分解并将分解结果累加到一个全局的质因数计数器中。最后将计数器中的所有指数加1后相乘即得答案。3. 算法实现与优化策略3.1 基础版本实现清晰的逻辑框架我们先实现一个最直接易懂的版本确保逻辑正确。def divisor_count_of_factorial(n): 计算 n! 的正约数个数。 # 用一个字典来记录所有质因子的总指数。key是质因子value是指数。 prime_counter {} # 遍历从2到n的每一个数1不影响质因数 for i in range(2, n 1): num i # 对当前数num进行质因数分解 p 2 while p * p num: while num % p 0: # 当p能整除num时 prime_counter[p] prime_counter.get(p, 0) 1 num // p p 1 # 循环结束后如果num大于1那么它本身就是一个质因子 if num 1: prime_counter[num] prime_counter.get(num, 0) 1 # 计算约数个数 result 1 for exp in prime_counter.values(): result * (exp 1) return result # 测试 print(divisor_count_of_factorial(10)) # 输出270 print(divisor_count_of_factorial(20)) # 输出... (可以快速计算)这个版本完全遵循了我们之前的思路。对于每个i我们都用试除法进行质因数分解。它的时间复杂度大致是O(n √n)对于n1000的竞赛范围基本够用但还有优化空间。3.2 关键优化基于素数筛的预处理上面的基础版本有一个明显的浪费对于每个数i我们都从2开始尝试整除其中包含了很多合数除数的判断。一个更高效的策略是预先用线性筛法或埃氏筛法求出n以内的所有素数然后只使用这些素数去分解i。def divisor_count_of_factorial_optimized(n): 优化版预先筛选素数使用素数列表进行分解。 # 步骤1使用埃拉托斯特尼筛法筛选出n以内的所有素数 is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) # 从i*i开始标记因为更小的倍数已经被之前的素数标记过了 for j in range(i * i, n 1, i): is_prime[j] False prime_counter {} # 步骤2遍历2到n只用素数进行分解 for i in range(2, n 1): num i # 只用预先生成的素数列表中的素数来试除 for p in primes: if p * p num: # 如果素数的平方大于当前数说明剩余部分是质数 break while num % p 0: prime_counter[p] prime_counter.get(p, 0) 1 num // p if num 1: # 这里的num一定是质数且是primes列表中的一个如果numn prime_counter[num] prime_counter.get(num, 0) 1 # 步骤3计算结果 result 1 for exp in prime_counter.values(): result * (exp 1) return result这个优化在n较大时比如n10^5优势明显因为避免了大量无用的合数试除。注意在埃氏筛法中内层循环从i*i开始是一个常见优化但需要注意当n很大时i*i可能会整数溢出在Python中无此问题或者在某些严格环境下为了绝对安全可以从i*2开始。不过对于竞赛题常见的n范围i*i是高效且安全的。3.3 进一步优化直接累计质因子指数我们还可以换一个角度思考。我们的目标不是得到每个数i的分解式而是最终n!的分解式。有没有办法不通过分解每个i直接得到质因子在n!中的总指数呢答案是肯定的这就是勒让德定理。对于任意质数pp在n!的质因数分解中的指数等于[n/p] [n/p^2] [n/p^3] ...其中[x]表示对x向下取整。这个公式的含义是1到n中有[n/p]个数是p的倍数至少贡献一个p有[n/p^2]个数是p^2的倍数在刚才的基础上再多贡献一个p以此类推。def divisor_count_of_factorial_legendre(n): 高效版使用勒让德定理直接计算每个质因子在n!中的指数。 # 步骤1筛选n以内的素数 is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) for j in range(i * i, n 1, i): is_prime[j] False result 1 # 步骤2对每个素数p应用勒让德定理 for p in primes: exp 0 power p while power n: exp n // power power * p # 计算 p, p^2, p^3, ... result * (exp 1) return result这个算法的时间复杂度约为O(n log log n π(n) log n)其中π(n)是n以内的素数个数。当n非常大时比如10^7这个方法的优势是压倒性的因为它完全避免了对每个数进行分解的循环。4. 代码实现细节与避坑指南4.1 边界条件与特殊输入处理一个健壮的程序必须考虑边界情况。n0或n1根据定义0! 11! 1。数字1只有一个正约数就是它本身。所以函数应该返回1。大数运算与溢出最终的结果约数个数可能非常大。例如100!的约数个数是一个巨大的数。在Python中整数可以无限大所以没有问题。但如果你用C或Java等语言需要使用long long甚至大数库。在我们的Python实现中直接相乘即可。我们需要在函数开头添加边界判断def divisor_count_of_factorial_final(n): if n 1: return 1 # ... 其余代码使用勒让德定理版本 ...4.2 数据结构的选择字典 vs 数组记录质因子指数我们用了字典prime_counter。它的好处是自适应只存储出现的质因子。另一种方法是使用一个长度为n1的数组exp_counter下标代表质因子值代表指数。对于素数筛优化版由于我们知道所有素数都小于等于n用数组也可以而且访问速度可能更快。但考虑到素数分布稀疏字典在内存使用上通常更优。在竞赛中两者均可字典写起来更简洁安全。4.3 算法选择建议如何根据场景决策面对一道具体的题目你该如何选择实现方法呢这里是我的经验如果n 10^3使用基础版本或素数筛优化版即可代码简单不易出错。如果10^3 n 10^6强烈推荐使用基于素数筛和勒让德定理的版本。这是竞赛中的标准解法。如果n 10^7需要更精细的优化。例如素数筛部分可以使用字节数组(bytearray)来减少内存勒让德定理的循环条件power n中power可能溢出在Python中会自动升级为长整数但速度慢可以改用while n // power 0作为条件。4.4 一个完整的、带注释的竞赛级代码下面给出一个整合了边界处理、素数筛和勒让德定理的最终版本并附上详细注释。def count_divisors_of_factorial(n): 计算 n! 的正约数个数。 采用埃氏筛勒让德定理时间复杂度约为 O(n log log n)。 Args: n: 正整数 Returns: n! 的正约数个数 # 边界条件处理 if n 1: return 1 # 1. 埃拉托斯特尼筛法求n以内所有素数 is_prime [True] * (n 1) primes [] # 0和1不是素数 is_prime[0] is_prime[1] False for i in range(2, n 1): if is_prime[i]: primes.append(i) # 从i*i开始标记非素数注意防止i*i溢出Python中无此问题 if i * i n: # 这个判断可以避免当i很大时不必要的循环 for j in range(i * i, n 1, i): is_prime[j] False # 2. 应用勒让德定理计算每个素数p在n!中的指数 result 1 for p in primes: exp 0 # 计算 n//p n//p^2 n//p^3 ... power p while power n: exp n // power power * p # 根据公式约数个数乘以 (exp 1) result * (exp 1) return result # 测试与验证 if __name__ __main__: # 测试一些小值可以用暴力法验证仅适用于很小的n def brute_force(n): import math fact math.factorial(n) cnt 0 for i in range(1, int(fact**0.5) 1): if fact % i 0: cnt 1 if i ! fact // i: cnt 1 return cnt test_cases [0, 1, 2, 5, 10, 20] for n in test_cases: my_ans count_divisors_of_factorial(n) if n 10: # 暴力法只能验证很小的n bf_ans brute_force(n) print(fn{n}: 我的结果{my_ans}, 暴力结果{bf_ans}, {正确 if my_ans bf_ans else 错误}) else: print(fn{n}: 结果{my_ans}) # 计算一个较大的值 print(f100! 的约数个数是: {count_divisors_of_factorial(100)})5. 实战扩展与常见问题排查5.1 问题变形计算n!的约数之和有时题目会变形成求n!的所有正约数之和。这同样可以利用质因数分解公式。 如果 N p1^a1 * p2^a2 * ... * pk^ak那么N的所有正约数之和S(N)为 S(N) (1 p1 p1^2 ... p1^a1) * (1 p2 p2^2 ... p2^a2) * ... * (1 pk pk^2 ... pk^ak) 每个括号内是一个等比数列求和等于 (p_i^(a_i1) - 1) / (p_i - 1)。 因此在求出每个质因子p及其在n!中的指数a后我们可以用快速幂计算 p^(a1)然后累乘求和公式即可。5.2 常见错误与调试技巧在实现过程中以下几个坑点需要特别注意循环条件错误在勒让德定理的实现中内层循环条件是while power n。一定要确保是因为当power n时n // power 1这一项需要被计入。如果写成就会漏掉一项。素数筛的初始化在埃氏筛中一定要记得将is_prime[0]和is_prime[1]显式地标记为False。虽然我们从2开始循环但有些情况下可能会意外访问到下标0和1。字典的默认值使用prime_counter.get(p, 0) 1是一种安全且简洁的写法。如果直接写prime_counter[p] 1需要在之前判断p是否在字典中否则会抛出KeyError。大数结果验证对于较大的n如100结果可能非常大。一个简单的验证方法是使用sympy库如果环境允许进行交叉验证。或者可以计算几个小n的值与已知数列OEIS A027423进行比对。性能瓶颈当n极大时如10^7即使是优化算法素数筛部分也可能成为内存和时间的瓶颈。此时可以考虑使用“分段筛”或更高效的“欧拉筛”线性筛。对于勒让德定理的计算当p变大后n//p会迅速变小循环次数很少所以主要开销在筛素数。5.3 复杂度分析与竞赛应用让我们分析一下最终版算法埃氏筛勒让德定理的复杂度时间复杂度埃氏筛的时间复杂度是O(n log log n)。对于每个素数p约有n/ln n个勒让德定理的循环会执行大约log_p n次。总时间主要受筛法支配可以认为是近似线性的。空间复杂度主要是is_prime布尔数组O(n)。对于n10^6大约需要1MB内存如果使用bytearray或bitset可以更少这在竞赛中是完全可接受的。在像蓝桥杯这样的竞赛中这道题通常属于“数论”或“基础算法”范畴难度中等。它完美地考察了选手以下几个能力1) 将数学定理转化为算法的能力2) 对算法复杂度敏感避免暴力求解3) 编写清晰、健壮代码的能力。掌握这个解法不仅能够解决这道题其背后的“质因数分解计数”思想还可以应用于许多其他问题比如计算组合数C(n, m)的约数个数、计算最大公约数的约数个数等等。 
长河君 · 2026/8/28 6:30:05 · 阅读 1.2k 从阶乘约数问题看质因数分解与勒让德定理的算法实践
1. 项目概述从一道竞赛题看约数计算的实战策略最近在辅导一些准备参加编程竞赛的同学发现“蓝桥杯”竞赛中一道关于“阶乘约数”的Python题目成了不少人的拦路虎。题目本身并不复杂就是给定一个正整数n要求计算n!n的阶乘的正约数个数。但很多初学者一看到题目第一反应就是先算出n!这个巨大的数然后再去遍历找约数——这个思路在n稍微大一点比如n20的时候程序就会直接卡死或者内存溢出。这其实是一个经典的“算法思维”与“暴力计算”的分水岭问题。它考察的不是你会不会写循环而是你是否理解数论中的核心原理并能够将其转化为高效的代码。今天我就结合自己多年刷题和教学的经验把这个问题的“里子”和“面子”都拆开来讲透让你不仅会做这道题更能掌握一类问题的通用解法。2. 核心思路拆解为什么不能直接计算阶乘2.1 问题本质与暴力法的陷阱我们先来直观感受一下暴力法为什么不可行。n的阶乘n! 1 × 2 × 3 × … × n。当n20时20! 2432902008176640000这已经是一个19位数。如果n100100!是一个158位的天文数字没有任何基本数据类型能直接存储它更别提对它进行遍历求约数了。所以这道题的核心约束就是禁止直接计算并分解大整数n!。我们必须寻找一个不依赖于大数运算的数学方法。2.2 数论基石正约数个数的计算公式解决这个问题的钥匙藏在数论里一个正整数N的正约数个数公式。假设我们将N进行质因数分解得到 N p1^a1 * p2^a2 * ... * pk^ak 其中p1, p2, ..., pk 是不同的质数a1, a2, ..., ak 是对应的指数。 那么N的正约数个数D(N)为 D(N) (a1 1) * (a2 1) * ... * (ak 1)这个公式怎么理解呢我们可以把每个约数想象成从各个质因子的“库存”中挑选数量。对于质因子p1我们可以挑0个、1个、…、a1个共有(a11)种选择。各个质因子的选择是独立的所以总的挑选方式即约数的个数就是每种选择数的乘积。2.3 从N到N!的思路转换现在我们的目标N变成了n!。n! 1×2×3×…×n。根据乘法结合律n!的质因数分解等于从1到n每个数字的质因数分解的“总和”。 举个例子计算10!的约数个数。 10! 10 × 9 × 8 × … × 2 × 1。 我们不需要算出3628800再分解而是可以分别分解每个乘数10 2 × 59 3²8 2³7 76 2 × 35 54 2²3 32 21 1 (忽略)然后我们把所有质因子的指数加起来 质因子2: 来自10(1次)、8(3次)、6(1次)、4(2次)、2(1次)。总计 13121 8次。 质因子3: 来自9(2次)、6(1次)、3(1次)。总计 211 4次。 质因子5: 来自10(1次)、5(1次)。总计 11 2次。 质因子7: 来自7(1次)。总计 1次。所以10! 2^8 × 3^4 × 5^2 × 7^1。 根据约数个数公式10!的约数个数 (81) × (41) × (21) × (11) 9 × 5 × 3 × 2 270。至此我们的算法蓝图就清晰了遍历从2到n的每一个整数i对i进行质因数分解并将分解结果累加到一个全局的质因数计数器中。最后将计数器中的所有指数加1后相乘即得答案。3. 算法实现与优化策略3.1 基础版本实现清晰的逻辑框架我们先实现一个最直接易懂的版本确保逻辑正确。def divisor_count_of_factorial(n): 计算 n! 的正约数个数。 # 用一个字典来记录所有质因子的总指数。key是质因子value是指数。 prime_counter {} # 遍历从2到n的每一个数1不影响质因数 for i in range(2, n 1): num i # 对当前数num进行质因数分解 p 2 while p * p num: while num % p 0: # 当p能整除num时 prime_counter[p] prime_counter.get(p, 0) 1 num // p p 1 # 循环结束后如果num大于1那么它本身就是一个质因子 if num 1: prime_counter[num] prime_counter.get(num, 0) 1 # 计算约数个数 result 1 for exp in prime_counter.values(): result * (exp 1) return result # 测试 print(divisor_count_of_factorial(10)) # 输出270 print(divisor_count_of_factorial(20)) # 输出... (可以快速计算)这个版本完全遵循了我们之前的思路。对于每个i我们都用试除法进行质因数分解。它的时间复杂度大致是O(n √n)对于n1000的竞赛范围基本够用但还有优化空间。3.2 关键优化基于素数筛的预处理上面的基础版本有一个明显的浪费对于每个数i我们都从2开始尝试整除其中包含了很多合数除数的判断。一个更高效的策略是预先用线性筛法或埃氏筛法求出n以内的所有素数然后只使用这些素数去分解i。def divisor_count_of_factorial_optimized(n): 优化版预先筛选素数使用素数列表进行分解。 # 步骤1使用埃拉托斯特尼筛法筛选出n以内的所有素数 is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) # 从i*i开始标记因为更小的倍数已经被之前的素数标记过了 for j in range(i * i, n 1, i): is_prime[j] False prime_counter {} # 步骤2遍历2到n只用素数进行分解 for i in range(2, n 1): num i # 只用预先生成的素数列表中的素数来试除 for p in primes: if p * p num: # 如果素数的平方大于当前数说明剩余部分是质数 break while num % p 0: prime_counter[p] prime_counter.get(p, 0) 1 num // p if num 1: # 这里的num一定是质数且是primes列表中的一个如果numn prime_counter[num] prime_counter.get(num, 0) 1 # 步骤3计算结果 result 1 for exp in prime_counter.values(): result * (exp 1) return result这个优化在n较大时比如n10^5优势明显因为避免了大量无用的合数试除。注意在埃氏筛法中内层循环从i*i开始是一个常见优化但需要注意当n很大时i*i可能会整数溢出在Python中无此问题或者在某些严格环境下为了绝对安全可以从i*2开始。不过对于竞赛题常见的n范围i*i是高效且安全的。3.3 进一步优化直接累计质因子指数我们还可以换一个角度思考。我们的目标不是得到每个数i的分解式而是最终n!的分解式。有没有办法不通过分解每个i直接得到质因子在n!中的总指数呢答案是肯定的这就是勒让德定理。对于任意质数pp在n!的质因数分解中的指数等于[n/p] [n/p^2] [n/p^3] ...其中[x]表示对x向下取整。这个公式的含义是1到n中有[n/p]个数是p的倍数至少贡献一个p有[n/p^2]个数是p^2的倍数在刚才的基础上再多贡献一个p以此类推。def divisor_count_of_factorial_legendre(n): 高效版使用勒让德定理直接计算每个质因子在n!中的指数。 # 步骤1筛选n以内的素数 is_prime [True] * (n 1) primes [] for i in range(2, n 1): if is_prime[i]: primes.append(i) for j in range(i * i, n 1, i): is_prime[j] False result 1 # 步骤2对每个素数p应用勒让德定理 for p in primes: exp 0 power p while power n: exp n // power power * p # 计算 p, p^2, p^3, ... result * (exp 1) return result这个算法的时间复杂度约为O(n log log n π(n) log n)其中π(n)是n以内的素数个数。当n非常大时比如10^7这个方法的优势是压倒性的因为它完全避免了对每个数进行分解的循环。4. 代码实现细节与避坑指南4.1 边界条件与特殊输入处理一个健壮的程序必须考虑边界情况。n0或n1根据定义0! 11! 1。数字1只有一个正约数就是它本身。所以函数应该返回1。大数运算与溢出最终的结果约数个数可能非常大。例如100!的约数个数是一个巨大的数。在Python中整数可以无限大所以没有问题。但如果你用C或Java等语言需要使用long long甚至大数库。在我们的Python实现中直接相乘即可。我们需要在函数开头添加边界判断def divisor_count_of_factorial_final(n): if n 1: return 1 # ... 其余代码使用勒让德定理版本 ...4.2 数据结构的选择字典 vs 数组记录质因子指数我们用了字典prime_counter。它的好处是自适应只存储出现的质因子。另一种方法是使用一个长度为n1的数组exp_counter下标代表质因子值代表指数。对于素数筛优化版由于我们知道所有素数都小于等于n用数组也可以而且访问速度可能更快。但考虑到素数分布稀疏字典在内存使用上通常更优。在竞赛中两者均可字典写起来更简洁安全。4.3 算法选择建议如何根据场景决策面对一道具体的题目你该如何选择实现方法呢这里是我的经验如果n 10^3使用基础版本或素数筛优化版即可代码简单不易出错。如果10^3 n 10^6强烈推荐使用基于素数筛和勒让德定理的版本。这是竞赛中的标准解法。如果n 10^7需要更精细的优化。例如素数筛部分可以使用字节数组(bytearray)来减少内存勒让德定理的循环条件power n中power可能溢出在Python中会自动升级为长整数但速度慢可以改用while n // power 0作为条件。4.4 一个完整的、带注释的竞赛级代码下面给出一个整合了边界处理、素数筛和勒让德定理的最终版本并附上详细注释。def count_divisors_of_factorial(n): 计算 n! 的正约数个数。 采用埃氏筛勒让德定理时间复杂度约为 O(n log log n)。 Args: n: 正整数 Returns: n! 的正约数个数 # 边界条件处理 if n 1: return 1 # 1. 埃拉托斯特尼筛法求n以内所有素数 is_prime [True] * (n 1) primes [] # 0和1不是素数 is_prime[0] is_prime[1] False for i in range(2, n 1): if is_prime[i]: primes.append(i) # 从i*i开始标记非素数注意防止i*i溢出Python中无此问题 if i * i n: # 这个判断可以避免当i很大时不必要的循环 for j in range(i * i, n 1, i): is_prime[j] False # 2. 应用勒让德定理计算每个素数p在n!中的指数 result 1 for p in primes: exp 0 # 计算 n//p n//p^2 n//p^3 ... power p while power n: exp n // power power * p # 根据公式约数个数乘以 (exp 1) result * (exp 1) return result # 测试与验证 if __name__ __main__: # 测试一些小值可以用暴力法验证仅适用于很小的n def brute_force(n): import math fact math.factorial(n) cnt 0 for i in range(1, int(fact**0.5) 1): if fact % i 0: cnt 1 if i ! fact // i: cnt 1 return cnt test_cases [0, 1, 2, 5, 10, 20] for n in test_cases: my_ans count_divisors_of_factorial(n) if n 10: # 暴力法只能验证很小的n bf_ans brute_force(n) print(fn{n}: 我的结果{my_ans}, 暴力结果{bf_ans}, {正确 if my_ans bf_ans else 错误}) else: print(fn{n}: 结果{my_ans}) # 计算一个较大的值 print(f100! 的约数个数是: {count_divisors_of_factorial(100)})5. 实战扩展与常见问题排查5.1 问题变形计算n!的约数之和有时题目会变形成求n!的所有正约数之和。这同样可以利用质因数分解公式。 如果 N p1^a1 * p2^a2 * ... * pk^ak那么N的所有正约数之和S(N)为 S(N) (1 p1 p1^2 ... p1^a1) * (1 p2 p2^2 ... p2^a2) * ... * (1 pk pk^2 ... pk^ak) 每个括号内是一个等比数列求和等于 (p_i^(a_i1) - 1) / (p_i - 1)。 因此在求出每个质因子p及其在n!中的指数a后我们可以用快速幂计算 p^(a1)然后累乘求和公式即可。5.2 常见错误与调试技巧在实现过程中以下几个坑点需要特别注意循环条件错误在勒让德定理的实现中内层循环条件是while power n。一定要确保是因为当power n时n // power 1这一项需要被计入。如果写成就会漏掉一项。素数筛的初始化在埃氏筛中一定要记得将is_prime[0]和is_prime[1]显式地标记为False。虽然我们从2开始循环但有些情况下可能会意外访问到下标0和1。字典的默认值使用prime_counter.get(p, 0) 1是一种安全且简洁的写法。如果直接写prime_counter[p] 1需要在之前判断p是否在字典中否则会抛出KeyError。大数结果验证对于较大的n如100结果可能非常大。一个简单的验证方法是使用sympy库如果环境允许进行交叉验证。或者可以计算几个小n的值与已知数列OEIS A027423进行比对。性能瓶颈当n极大时如10^7即使是优化算法素数筛部分也可能成为内存和时间的瓶颈。此时可以考虑使用“分段筛”或更高效的“欧拉筛”线性筛。对于勒让德定理的计算当p变大后n//p会迅速变小循环次数很少所以主要开销在筛素数。5.3 复杂度分析与竞赛应用让我们分析一下最终版算法埃氏筛勒让德定理的复杂度时间复杂度埃氏筛的时间复杂度是O(n log log n)。对于每个素数p约有n/ln n个勒让德定理的循环会执行大约log_p n次。总时间主要受筛法支配可以认为是近似线性的。空间复杂度主要是is_prime布尔数组O(n)。对于n10^6大约需要1MB内存如果使用bytearray或bitset可以更少这在竞赛中是完全可接受的。在像蓝桥杯这样的竞赛中这道题通常属于“数论”或“基础算法”范畴难度中等。它完美地考察了选手以下几个能力1) 将数学定理转化为算法的能力2) 对算法复杂度敏感避免暴力求解3) 编写清晰、健壮代码的能力。掌握这个解法不仅能够解决这道题其背后的“质因数分解计数”思想还可以应用于许多其他问题比如计算组合数C(n, m)的约数个数、计算最大公约数的约数个数等等。