1. 项目概述从“完数难题”看ACM竞赛中的质数模块在ACM国际大学生程序设计竞赛ICPC或者各类在线判题系统OJ的刷题路上质数和素数相关的题目绝对是一个绕不开的“老朋友”。很多新手看到“质数”、“素数”、“完数”这些词第一反应可能是数学课本里的概念觉得基础简单。但真正上手解题尤其是面对像“完数难题”这类综合题目时才会发现这里面的水有多深。它绝不仅仅是写一个循环判断整除那么简单而是涉及到算法效率的极致优化、数学性质的巧妙应用以及对边界条件的全面把控。所谓“完数难题”通常指那些需要你找出一定范围内所有完数或者判断一个数是否为完数的题目。完数又称完全数它所有的真因子即除了自身以外的约数之和恰好等于它本身。比如612328124714。而解决完数问题的核心又不可避免地回到了质数素数这个基石上——因为我们需要高效地求出一个数的所有因子。如果你用的还是从1遍历到n的暴力方法在n高达10^5甚至10^6时程序就会超时TLE。这就是为什么我们需要一个专门的“质数素数模块”来武装自己它是一套工具箱里面装着筛法求质数表、质因数分解、求约数个数和约数和等高效算法。掌握这个模块你不仅能秒杀“完数难题”更能应对约数个数、欧拉函数、最大公约数/最小公倍数等一系列数论题目。今天我们就来彻底拆解这个模块我会结合多年打比赛和出题的经验把原理、代码、坑点以及那些OJ上不会告诉你的优化技巧一次性讲透。2. 核心思路与算法选型为什么“筛法”是基石面对质数相关问题初学者最容易写出的代码就是一个is_prime函数里面一个循环从2到sqrt(n)判断是否能整除。对于单次查询这没问题。但ACM题目最常见的套路是给你一个上限N然后进行多次查询或者需要你预处理出N以内的所有质数。这时如果对每个查询都单独用sqrt(n)的方法判断总时间复杂度会爆炸。2.1 暴力判质法的局限性分析我们先看看最朴素的判断方法def is_prime_naive(n): if n 2: return False for i in range(2, int(n**0.5) 1): if n % i 0: return False return True这个方法的时间复杂度是O(√n)。假设题目要求我们找出[1, N]之间所有的质数那么总时间复杂度就是O(N√N)。当N10^6时这个计算量已经很大如果N10^7在普通的1秒时间限制内几乎不可能完成。因此我们需要一种能“批量”生产质数的方法。2.2 埃拉托斯特尼筛法埃筛的核心思想埃筛Sieve of Eratosthenes的智慧在于“反其道而行之”。我们不再专注于“一个数是不是质数”而是专注于“标记出所有不是质数的数合数”。算法步骤假设我们要处理的范围是[2, N]。我们创建一个长度为N1的布尔数组is_prime初始值全部设为True表示我们先假设所有数都是质数。从最小的质数2开始如果is_prime[2]是True那么我们知道2是质数。但更重要的是所有2的倍数4, 6, 8, ...都一定是合数。于是我们把is_prime[4],is_prime[6], ... 全部标记为False。接着看下一个数3。如果is_prime[3]是True它没有被之前的步骤标记为合数那么3是质数。同理我们把所有3的倍数6, 9, 12, ...标记为False。注意像6这样的数它既是2的倍数也是3的倍数会被重复标记但这不影响结果。继续这个过程。当我们遍历到数i时如果is_prime[i]仍然是True说明它没有被任何比它小的质数筛掉那么i就是质数我们再去标记i的所有倍数。什么时候停止呢我们只需要遍历到sqrt(N)。因为如果N有一个大于sqrt(N)的因子d那么它必然对应一个小于sqrt(N)的因子N/d。所以所有小于等于N的合数其最小质因子一定小于等于sqrt(N)。当我们用所有小于等于sqrt(N)的质数去筛过后剩下的就都是质数了。时间复杂度经过数学分析埃筛的时间复杂度是O(N log log N)。这是一个比O(N)略大但远小于O(N log N)的复杂度对于N10^7完全可以在1秒内完成。注意埃筛的“筛”字形象地描述了算法过程。它不是“判断”而是“排除”。这种思维转换是解决大规模质数问题的关键。2.3 线性筛欧拉筛的进一步优化埃筛虽然快但它有一个小缺点一个合数可能会被它的多个质因子重复标记比如30会被2、3、5各标记一次。当N极大比如10^8时这些重复操作会带来一定的常数时间开销。线性筛又称欧拉筛保证了每个合数只会被它的最小质因子筛掉一次从而将时间复杂度严格降到了O(N)。这是理论上的最优算法。算法核心它维护一个质数列表primes。对于每一个从2到N的数i如果i是质数即没有被之前的数筛掉就加入primes列表。无论i是不是质数都让i与当前primes列表中的质数p相乘去标记合数i * p。但这里有一个关键限制当i % p 0时必须立即停止。为什么假设i % p 0即i k * p。那么对于下一个质数p_next要标记的合数是i * p_next k * p * p_next。这个合数的最小质因子是p它本应该在未来当i增长到k * p_next时用质数p来筛掉。如果现在用p_next去筛就破坏了“每个合数只被最小质因子筛”的规则。线性筛的代码比埃筛稍复杂但在对效率有极致要求的场景下或者需要同步得到每个数的最小质因子时是首选。对于大部分ACM题目N ≤ 10^7埃筛的简洁和高效已经足够。3. 算法实现与代码细节从理论到AC代码理解了原理我们来看代码实现。我会分别给出Python和C两种语言在竞赛中最常用的版本并解释每一个细节和优化点。3.1 埃筛Sieve of Eratosthenes的标准实现与优化基础版本def sieve_eratosthenes(n): is_prime [True] * (n 1) # 创建数组包含0到n is_prime[0] is_prime[1] False # 0和1不是质数 for i in range(2, int(n**0.5) 1): # 只需遍历到根号n if is_prime[i]: # 从 i*i 开始标记因为比 i*i 小的 i 的倍数已经被更小的质数标记过了 for j in range(i * i, n 1, i): is_prime[j] False # 收集所有质数 primes [i for i in range(2, n1) if is_prime[i]] return primes, is_prime # 示例求100以内的质数 primes_list, is_prime_table sieve_eratosthenes(100) print(primes_list[:10]) # 输出前10个质数关键优化点解析遍历终点是int(n**0.5) 1这是由数学原理决定的前面已经解释过。这是最重要的优化没有它复杂度就不是O(N log log N)了。内层循环从i*i开始这是埃筛的一个经典优化。为什么可以从i*i开始考虑质数i5它的倍数有10, 15, 20, 25, 30... 注意10 2*5它在i2时已经被标记15 3*5在i3时被标记20 4*54不是质数但20 2*10其最小质因子是2已在i2时被标记。所以对于质数i所有小于i*i的i的倍数其最小质因子都小于i因此肯定已经被之前的质数筛过了。直接从i*i开始筛避免了大量重复操作。使用布尔数组is_prime在Python中使用listofbool。在C中强烈建议使用vectorbool或bitset因为它们经过特化每个bool只占1 bit可以极大节省内存对于N10^7vectorint会占用约40MB而vectorbool只需约1.25MB。内存节省意味着缓存命中率更高速度更快。C优化版本使用vectorbool#include iostream #include vector using namespace std; vectorint sieve_eratosthenes(int n) { vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; vectorint primes; for (int i 2; i * i n; i) { // 用 i*i n 代替 i sqrt(n)避免浮点数运算 if (is_prime[i]) { // 这里注意i*i可能超过int范围如果n很大需要用long long for (long long j (long long)i * i; j n; j i) { is_prime[j] false; } } } for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } } return primes; }3.2 线性筛欧拉筛的实现线性筛的代码逻辑更精巧需要仔细理解内层循环的跳出条件。def linear_sieve(n): is_prime [True] * (n 1) primes [] # 存放所有质数 for i in range(2, n 1): if is_prime[i]: primes.append(i) # 关键步骤用当前数 i 乘以质数列表里的质数 for p in primes: if i * p n: # 超过范围中断 break is_prime[i * p] False if i % p 0: # 核心保证每个合数只被最小质因子筛一次 break return primes, is_prime代码逐行解读if is_prime[i]: primes.append(i)如果i是质数收入列表。内层循环for p in primes尝试用当前数i去乘以前面找到的所有质数。if i * p n: break确保只标记范围内的数。is_prime[i * p] False标记合数i * p。if i % p 0: break这是灵魂所在。当p能整除i时p就是i的最小质因子因为primes是从小到大遍历的。此时对于合数i * p其最小质因子就是p。如果我们继续用更大的质数p_next去乘i得到的合数i * p_next的最小质因子仍然是p因为i里已经包含p而不是p_next。这就违反了“用最小质因子筛”的原则。所以必须break。线性筛的独特优势真正的O(N)时间复杂度。在筛的过程中自然地得到了每个数的最小质因子就是内层循环break时的那个p。这个信息在后续的质因数分解、求欧拉函数等操作中非常有用。实操心得对于绝大部分题目埃筛的代码更短、更直观不易写错且效率足够。我建议新手先熟练掌握埃筛。只有当题目明确要求极致性能N接近10^8或者你需要同步处理每个数的质因数时再考虑使用线性筛。4. 攻克“完数难题”应用质数模块求解现在我们手握高效的质数筛法可以回头来解决“完数难题”了。完数的定义是一个数等于它的所有真因子之和。真因子包括1但不包括它自身。4.1 暴力求解法与它的效率瓶颈最直接的想法是对于一个数n遍历从1到n-1的所有数判断是否是n的因子然后求和。def is_perfect_number_naive(n): factor_sum 0 for i in range(1, n): if n % i 0: factor_sum i return factor_sum n这个方法的时间复杂度是O(n)。找10000以内的完数尚可但题目范围一旦变大比如n在10^6这个量级或者要求你输出某个区间内所有完数这个算法就完全不可行了。4.2 利用因子成对性质进行优化优化思路来自于一个简单的数学事实如果i是n的因子那么n/i也一定是n的因子。并且除了完全平方数的情况i和n/i是一对不同的因子。因此我们只需要遍历从1到sqrt(n)。当i能整除n时我们找到了两个因子i和n/i。需要小心处理边界如果i n/i即n是完全平方数那么这个因子只能加一次。另外因子n本身即当i1时n/i n不能加入求和。def is_perfect_number_optimized(n): if n 1: return False factor_sum 1 # 1一定是因子先加上 i 2 while i * i n: # 遍历到根号n if n % i 0: factor_sum i # 加入对应的另一个因子但要避免重复加入n本身 j n // i if i ! j: # 如果不是平方根则加入另一个因子 factor_sum j i 1 return factor_sum n这个优化将时间复杂度从O(n)降到了O(√n)是一个巨大的飞跃。对于单个数的判断这已经足够高效。4.3 结合质数筛法的预处理思路但是ACM题目常常不是问单个数而是问一个区间内有多少完数或者列出所有完数。例如“找出10000以内的所有完数”。这时我们对区间内每个数都用O(√n)的方法判断总复杂度是O(N√N)对于N10^5可能还行对于N10^6就压力山大了。有没有更快的批量处理方法遗憾的是完数本身没有像质数那样的高效“筛法”。已知的完数非常少并且都与梅森素数有关一个偶数是完数当且仅当它可以写成2^(p-1) * (2^p - 1)的形式其中2^p - 1是梅森素数。在竞赛范围内题目给出的范围通常不会太大比如N10^8使得区间内完数的个数极少实际上10^8以内的完数只有5个6, 28, 496, 8128, 33550336。因此竞赛中的标准做法是打表法如果题目范围固定且不大直接预先计算好范围内的所有完数把结果硬编码到程序里。这是时间复杂度O(1)的“作弊”方法但非常有效。# 已知 10^7 以内的完数只有这4个 perfect_numbers_in_10e7 [6, 28, 496, 8128] def is_perfect_by_table(n): return n in perfect_numbers_in_10e7预处理每个数的真因子和这需要用到质数筛法的思想延伸。我们可以用一个类似“筛法”的过程来快速求出[1, N]内每个数的所有因子和。思路初始化一个数组sum_of_factors长度为N1全部为1因为1是所有数的因子。然后我们模仿埃筛的过程。对于每个数i从2开始我们把i加到它的所有倍数j的sum_of_factors[j]上。因为i是j的因子。这个过程结束后sum_of_factors[n]就包含了n的所有因子包括1和n本身的和。那么n的真因子和就是sum_of_factors[n] - n。时间复杂度这个“因子和筛法”的复杂度是O(N log N)因为对于每个i我们要操作N/i个倍数。比O(N√N)要好但比质数筛法慢。当N10^6时这个方法是可行的。def sum_of_proper_factors_sieve(n): # 初始化所有数的因子和先算上1 factor_sum [1] * (n 1) factor_sum[0] 0 # 0没有因子 for i in range(2, n // 2 1): # i最大可以是n/2因为超过n/2的数不可能是其他数除了自己的因子 for j in range(2 * i, n 1, i): # 把i加到它的所有倍数j的因子和上 factor_sum[j] i # 现在 factor_sum[i] 存储的是 i 的所有因子包括1和i的和 # 真因子和 factor_sum[i] - i perfect_numbers [] for i in range(2, n 1): if factor_sum[i] i * 2: # 因为factor_sum[i]包含了i本身所以判断是否等于 2*i # 或者 if factor_sum[i] - i i: perfect_numbers.append(i) return perfect_numbers # 找出10000以内的完数 print(sum_of_proper_factors_sieve(10000)) # 输出: [6, 28, 496, 8128]注意事项这个“因子和筛法”在内存和时间上都有开销。对于N10^7factor_sum数组需要约80MB内存如果使用Python的listofint每个int在64位系统占28字节内存会爆掉。在C中使用vectorint4字节每个需要约40MB是可行的边界。因此一定要根据题目给定的数据范围来选择算法。范围小N≤10^5可以用优化后的单点判断范围中等N≤10^6可以考虑因子和筛法范围大但完数已知很少直接用打表法。5. 常见问题与实战调试技巧即使理解了算法在编码和调试过程中还是会遇到各种坑。这里我总结几个最常见的问题和解决方法。5.1 数组越界与整数溢出这是使用筛法时最常犯的错误。埃筛内层循环的起始点for j in range(i*i, n1, i)。当i很大时i*i可能会超过n甚至超过整数类型的最大值导致溢出或循环条件错误。在C中必须使用long long类型来存储i*i。// 错误示范i是inti*i可能溢出 for (int j i * i; j n; j i) // 正确示范 for (long long j (long long)i * i; j n; j i)在Python中整数是任意精度的没有溢出问题但逻辑正确性仍需保证。数组大小我们通常创建长度为n1的数组来方便下标直接对应数字。一定要确保访问is_prime[n]时不会越界。在遍历时循环条件通常是i n或i n1。5.2 输入输出与性能优化ACM竞赛对程序的运行时间和内存有严格限制。关闭流同步C如果混用cin/cout和scanf/printf或者需要大量输入输出时在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);可以显著提升cin/cout的速度。使用sys.stdin.read()Python对于海量输入比如10^5行以上使用input()会非常慢。应该使用sys.stdin.buffer.read()一次性读入再解析。import sys data sys.stdin.buffer.read().split() # data现在是字节列表需要转换 n int(data[0])避免不必要的函数调用和拷贝在循环内部创建大的临时列表/字符串会严重影响性能。5.3 典型错误案例求质数个数题目给定n求小于n的质数个数。n 10^7。错误代码示例Pythondef count_primes_wrong(n): count 0 for i in range(2, n): if is_prime_naive(i): # 对每个数都用O(√i)的函数判断 count 1 return count这个代码的时间复杂度是O(n√n)对于n10^6可能就超时了。正确做法使用埃筛或线性筛预处理出is_prime数组然后遍历计数时间复杂度O(N log log N)或O(N)。def count_primes(n): if n 2: return 0 is_prime [True] * n is_prime[0] is_prime[1] False for i in range(2, int(n**0.5)1): if is_prime[i]: for j in range(i*i, n, i): is_prime[j] False return sum(is_prime) # 直接对布尔数组求和True会被当作15.4 调试技巧小数据验证与打印中间结果从小数据开始先用n20, 30这样的小数据测试你的筛法手动列出质数表进行对比。确保基础逻辑正确。打印中间数组在调试时可以把is_prime数组打印出来比如n30检查每个位置的值是否符合预期。这对于排查线性筛的逻辑错误特别有用。对拍写一个暴力但正确的算法比如is_prime_naive和你的优化算法在随机生成的小数据范围内比如n1000进行对比确保结果一致。6. 知识延伸与题目变式掌握了质数筛法和完数求解你已经解决了这个模块的核心问题。但ACM中的数论题千变万化这里给出几个常见的延伸方向和变式题目帮助你举一反三。6.1 质因数分解质因数分解是很多数论问题的基础。利用筛法我们可以预处理出每个数的最小质因子线性筛天然就能得到从而实现O(log n)的质因数分解。# 假设我们已经用线性筛得到了 min_prime 数组min_prime[x] 表示x的最小质因子 # 线性筛过程中可以记录if i % p 0: min_factor[i * p] p; else: min_factor[i * p] p; def factorize(n, min_prime): factors [] while n 1: p min_prime[n] cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) # (质因子, 指数) return factors6.2 求约数个数与约数和一个数n的质因数分解形式为n p1^a1 * p2^a2 * ... * pk^ak。约数个数d(n) (a11) * (a21) * ... * (ak1)约数和σ(n) (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)在得到质因数分解后这两个值可以快速计算。这可以用来解决“求范围内约数个数最多的数”之类的问题。6.3 欧拉函数Euler‘s Totient Function欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数。它也可以通过质因数分解计算φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)同样利用线性筛我们可以在O(N)时间内预处理出[1, N]内所有数的欧拉函数值。这是一个非常重要的数论函数在模运算、 RSA加密等领域有应用。6.4 相关题目推荐素数判定/素数个数最基础的题目用于练习筛法。POJ 2689 Prime Distance求区间素数需要二次筛法是一道经典难题。完数判定HDU 1406 完数直接应用本文的优化判断或打表法即可。亲和数如果两个数每个数的所有真因子之和等于另一个数则称它们为亲和数。如(220, 284)。这需要计算并比较真因子和是完数问题的简单变种。求最大质因子SPOJ PFDIV需要高效的质因数分解。求约数个数POJ 2992 Divisors需要组合数学和质因数分解知识。质数模块是ACM数论的地基看起来简单但想做到又快又准需要大量的练习和对细节的把握。从理解筛法的“排除”思想到写出无懈可击的代码再到能灵活应用于约数、因子和等问题这个过程是算法能力的一次扎实提升。多写多调多总结当你再看到“质数”、“完数”这些词时心里有的将不再是畏惧而是一套清晰的解决路径和一行行稳健的代码。
1. 项目概述从“完数难题”看ACM竞赛中的质数模块在ACM国际大学生程序设计竞赛ICPC或者各类在线判题系统OJ的刷题路上质数和素数相关的题目绝对是一个绕不开的“老朋友”。很多新手看到“质数”、“素数”、“完数”这些词第一反应可能是数学课本里的概念觉得基础简单。但真正上手解题尤其是面对像“完数难题”这类综合题目时才会发现这里面的水有多深。它绝不仅仅是写一个循环判断整除那么简单而是涉及到算法效率的极致优化、数学性质的巧妙应用以及对边界条件的全面把控。所谓“完数难题”通常指那些需要你找出一定范围内所有完数或者判断一个数是否为完数的题目。完数又称完全数它所有的真因子即除了自身以外的约数之和恰好等于它本身。比如612328124714。而解决完数问题的核心又不可避免地回到了质数素数这个基石上——因为我们需要高效地求出一个数的所有因子。如果你用的还是从1遍历到n的暴力方法在n高达10^5甚至10^6时程序就会超时TLE。这就是为什么我们需要一个专门的“质数素数模块”来武装自己它是一套工具箱里面装着筛法求质数表、质因数分解、求约数个数和约数和等高效算法。掌握这个模块你不仅能秒杀“完数难题”更能应对约数个数、欧拉函数、最大公约数/最小公倍数等一系列数论题目。今天我们就来彻底拆解这个模块我会结合多年打比赛和出题的经验把原理、代码、坑点以及那些OJ上不会告诉你的优化技巧一次性讲透。2. 核心思路与算法选型为什么“筛法”是基石面对质数相关问题初学者最容易写出的代码就是一个is_prime函数里面一个循环从2到sqrt(n)判断是否能整除。对于单次查询这没问题。但ACM题目最常见的套路是给你一个上限N然后进行多次查询或者需要你预处理出N以内的所有质数。这时如果对每个查询都单独用sqrt(n)的方法判断总时间复杂度会爆炸。2.1 暴力判质法的局限性分析我们先看看最朴素的判断方法def is_prime_naive(n): if n 2: return False for i in range(2, int(n**0.5) 1): if n % i 0: return False return True这个方法的时间复杂度是O(√n)。假设题目要求我们找出[1, N]之间所有的质数那么总时间复杂度就是O(N√N)。当N10^6时这个计算量已经很大如果N10^7在普通的1秒时间限制内几乎不可能完成。因此我们需要一种能“批量”生产质数的方法。2.2 埃拉托斯特尼筛法埃筛的核心思想埃筛Sieve of Eratosthenes的智慧在于“反其道而行之”。我们不再专注于“一个数是不是质数”而是专注于“标记出所有不是质数的数合数”。算法步骤假设我们要处理的范围是[2, N]。我们创建一个长度为N1的布尔数组is_prime初始值全部设为True表示我们先假设所有数都是质数。从最小的质数2开始如果is_prime[2]是True那么我们知道2是质数。但更重要的是所有2的倍数4, 6, 8, ...都一定是合数。于是我们把is_prime[4],is_prime[6], ... 全部标记为False。接着看下一个数3。如果is_prime[3]是True它没有被之前的步骤标记为合数那么3是质数。同理我们把所有3的倍数6, 9, 12, ...标记为False。注意像6这样的数它既是2的倍数也是3的倍数会被重复标记但这不影响结果。继续这个过程。当我们遍历到数i时如果is_prime[i]仍然是True说明它没有被任何比它小的质数筛掉那么i就是质数我们再去标记i的所有倍数。什么时候停止呢我们只需要遍历到sqrt(N)。因为如果N有一个大于sqrt(N)的因子d那么它必然对应一个小于sqrt(N)的因子N/d。所以所有小于等于N的合数其最小质因子一定小于等于sqrt(N)。当我们用所有小于等于sqrt(N)的质数去筛过后剩下的就都是质数了。时间复杂度经过数学分析埃筛的时间复杂度是O(N log log N)。这是一个比O(N)略大但远小于O(N log N)的复杂度对于N10^7完全可以在1秒内完成。注意埃筛的“筛”字形象地描述了算法过程。它不是“判断”而是“排除”。这种思维转换是解决大规模质数问题的关键。2.3 线性筛欧拉筛的进一步优化埃筛虽然快但它有一个小缺点一个合数可能会被它的多个质因子重复标记比如30会被2、3、5各标记一次。当N极大比如10^8时这些重复操作会带来一定的常数时间开销。线性筛又称欧拉筛保证了每个合数只会被它的最小质因子筛掉一次从而将时间复杂度严格降到了O(N)。这是理论上的最优算法。算法核心它维护一个质数列表primes。对于每一个从2到N的数i如果i是质数即没有被之前的数筛掉就加入primes列表。无论i是不是质数都让i与当前primes列表中的质数p相乘去标记合数i * p。但这里有一个关键限制当i % p 0时必须立即停止。为什么假设i % p 0即i k * p。那么对于下一个质数p_next要标记的合数是i * p_next k * p * p_next。这个合数的最小质因子是p它本应该在未来当i增长到k * p_next时用质数p来筛掉。如果现在用p_next去筛就破坏了“每个合数只被最小质因子筛”的规则。线性筛的代码比埃筛稍复杂但在对效率有极致要求的场景下或者需要同步得到每个数的最小质因子时是首选。对于大部分ACM题目N ≤ 10^7埃筛的简洁和高效已经足够。3. 算法实现与代码细节从理论到AC代码理解了原理我们来看代码实现。我会分别给出Python和C两种语言在竞赛中最常用的版本并解释每一个细节和优化点。3.1 埃筛Sieve of Eratosthenes的标准实现与优化基础版本def sieve_eratosthenes(n): is_prime [True] * (n 1) # 创建数组包含0到n is_prime[0] is_prime[1] False # 0和1不是质数 for i in range(2, int(n**0.5) 1): # 只需遍历到根号n if is_prime[i]: # 从 i*i 开始标记因为比 i*i 小的 i 的倍数已经被更小的质数标记过了 for j in range(i * i, n 1, i): is_prime[j] False # 收集所有质数 primes [i for i in range(2, n1) if is_prime[i]] return primes, is_prime # 示例求100以内的质数 primes_list, is_prime_table sieve_eratosthenes(100) print(primes_list[:10]) # 输出前10个质数关键优化点解析遍历终点是int(n**0.5) 1这是由数学原理决定的前面已经解释过。这是最重要的优化没有它复杂度就不是O(N log log N)了。内层循环从i*i开始这是埃筛的一个经典优化。为什么可以从i*i开始考虑质数i5它的倍数有10, 15, 20, 25, 30... 注意10 2*5它在i2时已经被标记15 3*5在i3时被标记20 4*54不是质数但20 2*10其最小质因子是2已在i2时被标记。所以对于质数i所有小于i*i的i的倍数其最小质因子都小于i因此肯定已经被之前的质数筛过了。直接从i*i开始筛避免了大量重复操作。使用布尔数组is_prime在Python中使用listofbool。在C中强烈建议使用vectorbool或bitset因为它们经过特化每个bool只占1 bit可以极大节省内存对于N10^7vectorint会占用约40MB而vectorbool只需约1.25MB。内存节省意味着缓存命中率更高速度更快。C优化版本使用vectorbool#include iostream #include vector using namespace std; vectorint sieve_eratosthenes(int n) { vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; vectorint primes; for (int i 2; i * i n; i) { // 用 i*i n 代替 i sqrt(n)避免浮点数运算 if (is_prime[i]) { // 这里注意i*i可能超过int范围如果n很大需要用long long for (long long j (long long)i * i; j n; j i) { is_prime[j] false; } } } for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } } return primes; }3.2 线性筛欧拉筛的实现线性筛的代码逻辑更精巧需要仔细理解内层循环的跳出条件。def linear_sieve(n): is_prime [True] * (n 1) primes [] # 存放所有质数 for i in range(2, n 1): if is_prime[i]: primes.append(i) # 关键步骤用当前数 i 乘以质数列表里的质数 for p in primes: if i * p n: # 超过范围中断 break is_prime[i * p] False if i % p 0: # 核心保证每个合数只被最小质因子筛一次 break return primes, is_prime代码逐行解读if is_prime[i]: primes.append(i)如果i是质数收入列表。内层循环for p in primes尝试用当前数i去乘以前面找到的所有质数。if i * p n: break确保只标记范围内的数。is_prime[i * p] False标记合数i * p。if i % p 0: break这是灵魂所在。当p能整除i时p就是i的最小质因子因为primes是从小到大遍历的。此时对于合数i * p其最小质因子就是p。如果我们继续用更大的质数p_next去乘i得到的合数i * p_next的最小质因子仍然是p因为i里已经包含p而不是p_next。这就违反了“用最小质因子筛”的原则。所以必须break。线性筛的独特优势真正的O(N)时间复杂度。在筛的过程中自然地得到了每个数的最小质因子就是内层循环break时的那个p。这个信息在后续的质因数分解、求欧拉函数等操作中非常有用。实操心得对于绝大部分题目埃筛的代码更短、更直观不易写错且效率足够。我建议新手先熟练掌握埃筛。只有当题目明确要求极致性能N接近10^8或者你需要同步处理每个数的质因数时再考虑使用线性筛。4. 攻克“完数难题”应用质数模块求解现在我们手握高效的质数筛法可以回头来解决“完数难题”了。完数的定义是一个数等于它的所有真因子之和。真因子包括1但不包括它自身。4.1 暴力求解法与它的效率瓶颈最直接的想法是对于一个数n遍历从1到n-1的所有数判断是否是n的因子然后求和。def is_perfect_number_naive(n): factor_sum 0 for i in range(1, n): if n % i 0: factor_sum i return factor_sum n这个方法的时间复杂度是O(n)。找10000以内的完数尚可但题目范围一旦变大比如n在10^6这个量级或者要求你输出某个区间内所有完数这个算法就完全不可行了。4.2 利用因子成对性质进行优化优化思路来自于一个简单的数学事实如果i是n的因子那么n/i也一定是n的因子。并且除了完全平方数的情况i和n/i是一对不同的因子。因此我们只需要遍历从1到sqrt(n)。当i能整除n时我们找到了两个因子i和n/i。需要小心处理边界如果i n/i即n是完全平方数那么这个因子只能加一次。另外因子n本身即当i1时n/i n不能加入求和。def is_perfect_number_optimized(n): if n 1: return False factor_sum 1 # 1一定是因子先加上 i 2 while i * i n: # 遍历到根号n if n % i 0: factor_sum i # 加入对应的另一个因子但要避免重复加入n本身 j n // i if i ! j: # 如果不是平方根则加入另一个因子 factor_sum j i 1 return factor_sum n这个优化将时间复杂度从O(n)降到了O(√n)是一个巨大的飞跃。对于单个数的判断这已经足够高效。4.3 结合质数筛法的预处理思路但是ACM题目常常不是问单个数而是问一个区间内有多少完数或者列出所有完数。例如“找出10000以内的所有完数”。这时我们对区间内每个数都用O(√n)的方法判断总复杂度是O(N√N)对于N10^5可能还行对于N10^6就压力山大了。有没有更快的批量处理方法遗憾的是完数本身没有像质数那样的高效“筛法”。已知的完数非常少并且都与梅森素数有关一个偶数是完数当且仅当它可以写成2^(p-1) * (2^p - 1)的形式其中2^p - 1是梅森素数。在竞赛范围内题目给出的范围通常不会太大比如N10^8使得区间内完数的个数极少实际上10^8以内的完数只有5个6, 28, 496, 8128, 33550336。因此竞赛中的标准做法是打表法如果题目范围固定且不大直接预先计算好范围内的所有完数把结果硬编码到程序里。这是时间复杂度O(1)的“作弊”方法但非常有效。# 已知 10^7 以内的完数只有这4个 perfect_numbers_in_10e7 [6, 28, 496, 8128] def is_perfect_by_table(n): return n in perfect_numbers_in_10e7预处理每个数的真因子和这需要用到质数筛法的思想延伸。我们可以用一个类似“筛法”的过程来快速求出[1, N]内每个数的所有因子和。思路初始化一个数组sum_of_factors长度为N1全部为1因为1是所有数的因子。然后我们模仿埃筛的过程。对于每个数i从2开始我们把i加到它的所有倍数j的sum_of_factors[j]上。因为i是j的因子。这个过程结束后sum_of_factors[n]就包含了n的所有因子包括1和n本身的和。那么n的真因子和就是sum_of_factors[n] - n。时间复杂度这个“因子和筛法”的复杂度是O(N log N)因为对于每个i我们要操作N/i个倍数。比O(N√N)要好但比质数筛法慢。当N10^6时这个方法是可行的。def sum_of_proper_factors_sieve(n): # 初始化所有数的因子和先算上1 factor_sum [1] * (n 1) factor_sum[0] 0 # 0没有因子 for i in range(2, n // 2 1): # i最大可以是n/2因为超过n/2的数不可能是其他数除了自己的因子 for j in range(2 * i, n 1, i): # 把i加到它的所有倍数j的因子和上 factor_sum[j] i # 现在 factor_sum[i] 存储的是 i 的所有因子包括1和i的和 # 真因子和 factor_sum[i] - i perfect_numbers [] for i in range(2, n 1): if factor_sum[i] i * 2: # 因为factor_sum[i]包含了i本身所以判断是否等于 2*i # 或者 if factor_sum[i] - i i: perfect_numbers.append(i) return perfect_numbers # 找出10000以内的完数 print(sum_of_proper_factors_sieve(10000)) # 输出: [6, 28, 496, 8128]注意事项这个“因子和筛法”在内存和时间上都有开销。对于N10^7factor_sum数组需要约80MB内存如果使用Python的listofint每个int在64位系统占28字节内存会爆掉。在C中使用vectorint4字节每个需要约40MB是可行的边界。因此一定要根据题目给定的数据范围来选择算法。范围小N≤10^5可以用优化后的单点判断范围中等N≤10^6可以考虑因子和筛法范围大但完数已知很少直接用打表法。5. 常见问题与实战调试技巧即使理解了算法在编码和调试过程中还是会遇到各种坑。这里我总结几个最常见的问题和解决方法。5.1 数组越界与整数溢出这是使用筛法时最常犯的错误。埃筛内层循环的起始点for j in range(i*i, n1, i)。当i很大时i*i可能会超过n甚至超过整数类型的最大值导致溢出或循环条件错误。在C中必须使用long long类型来存储i*i。// 错误示范i是inti*i可能溢出 for (int j i * i; j n; j i) // 正确示范 for (long long j (long long)i * i; j n; j i)在Python中整数是任意精度的没有溢出问题但逻辑正确性仍需保证。数组大小我们通常创建长度为n1的数组来方便下标直接对应数字。一定要确保访问is_prime[n]时不会越界。在遍历时循环条件通常是i n或i n1。5.2 输入输出与性能优化ACM竞赛对程序的运行时间和内存有严格限制。关闭流同步C如果混用cin/cout和scanf/printf或者需要大量输入输出时在main函数开头加上ios::sync_with_stdio(false); cin.tie(nullptr);可以显著提升cin/cout的速度。使用sys.stdin.read()Python对于海量输入比如10^5行以上使用input()会非常慢。应该使用sys.stdin.buffer.read()一次性读入再解析。import sys data sys.stdin.buffer.read().split() # data现在是字节列表需要转换 n int(data[0])避免不必要的函数调用和拷贝在循环内部创建大的临时列表/字符串会严重影响性能。5.3 典型错误案例求质数个数题目给定n求小于n的质数个数。n 10^7。错误代码示例Pythondef count_primes_wrong(n): count 0 for i in range(2, n): if is_prime_naive(i): # 对每个数都用O(√i)的函数判断 count 1 return count这个代码的时间复杂度是O(n√n)对于n10^6可能就超时了。正确做法使用埃筛或线性筛预处理出is_prime数组然后遍历计数时间复杂度O(N log log N)或O(N)。def count_primes(n): if n 2: return 0 is_prime [True] * n is_prime[0] is_prime[1] False for i in range(2, int(n**0.5)1): if is_prime[i]: for j in range(i*i, n, i): is_prime[j] False return sum(is_prime) # 直接对布尔数组求和True会被当作15.4 调试技巧小数据验证与打印中间结果从小数据开始先用n20, 30这样的小数据测试你的筛法手动列出质数表进行对比。确保基础逻辑正确。打印中间数组在调试时可以把is_prime数组打印出来比如n30检查每个位置的值是否符合预期。这对于排查线性筛的逻辑错误特别有用。对拍写一个暴力但正确的算法比如is_prime_naive和你的优化算法在随机生成的小数据范围内比如n1000进行对比确保结果一致。6. 知识延伸与题目变式掌握了质数筛法和完数求解你已经解决了这个模块的核心问题。但ACM中的数论题千变万化这里给出几个常见的延伸方向和变式题目帮助你举一反三。6.1 质因数分解质因数分解是很多数论问题的基础。利用筛法我们可以预处理出每个数的最小质因子线性筛天然就能得到从而实现O(log n)的质因数分解。# 假设我们已经用线性筛得到了 min_prime 数组min_prime[x] 表示x的最小质因子 # 线性筛过程中可以记录if i % p 0: min_factor[i * p] p; else: min_factor[i * p] p; def factorize(n, min_prime): factors [] while n 1: p min_prime[n] cnt 0 while n % p 0: n // p cnt 1 factors.append((p, cnt)) # (质因子, 指数) return factors6.2 求约数个数与约数和一个数n的质因数分解形式为n p1^a1 * p2^a2 * ... * pk^ak。约数个数d(n) (a11) * (a21) * ... * (ak1)约数和σ(n) (p1^(a11)-1)/(p1-1) * (p2^(a21)-1)/(p2-1) * ... * (pk^(ak1)-1)/(pk-1)在得到质因数分解后这两个值可以快速计算。这可以用来解决“求范围内约数个数最多的数”之类的问题。6.3 欧拉函数Euler‘s Totient Function欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数。它也可以通过质因数分解计算φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)同样利用线性筛我们可以在O(N)时间内预处理出[1, N]内所有数的欧拉函数值。这是一个非常重要的数论函数在模运算、 RSA加密等领域有应用。6.4 相关题目推荐素数判定/素数个数最基础的题目用于练习筛法。POJ 2689 Prime Distance求区间素数需要二次筛法是一道经典难题。完数判定HDU 1406 完数直接应用本文的优化判断或打表法即可。亲和数如果两个数每个数的所有真因子之和等于另一个数则称它们为亲和数。如(220, 284)。这需要计算并比较真因子和是完数问题的简单变种。求最大质因子SPOJ PFDIV需要高效的质因数分解。求约数个数POJ 2992 Divisors需要组合数学和质因数分解知识。质数模块是ACM数论的地基看起来简单但想做到又快又准需要大量的练习和对细节的把握。从理解筛法的“排除”思想到写出无懈可击的代码再到能灵活应用于约数、因子和等问题这个过程是算法能力的一次扎实提升。多写多调多总结当你再看到“质数”、“完数”这些词时心里有的将不再是畏惧而是一套清晰的解决路径和一行行稳健的代码。
