1. 项目概述从暴力枚举到高效筛法在编程和算法学习的路上质数也叫素数绝对是一个绕不开的经典话题。无论是刚入门时练习循环和条件判断还是后续接触算法优化判断一个数是不是质数、找出一定范围内的所有质数都是检验基本功的绝佳试金石。很多朋友一开始接触这个问题最直观的想法就是“暴力枚举”对于一个数n从2开始一直除到n-1看有没有能整除它的数。这个方法简单直接但效率也是最低的一旦n稍微大点比如上百万程序就得跑上好一会儿。这其实就是算法中“时间复杂度”概念的生动体现。暴力法的时间复杂度是O(n)对于单个大数尚可忍受但如果要求1到100万之间的所有质数对每个数都来一遍O(n)的检查那总的时间复杂度就飙升到了O(n²)几乎是不可接受的。于是先贤们发明了“筛法”——一种通过“筛选”来批量找出质数的高效算法。它不像暴力法那样一个个去“判断”而是巧妙地“排除”掉一定范围内的所有合数剩下的自然就是质数了。这就像用筛子筛沙子把细沙质数留下把粗颗粒合数筛掉。今天要深入聊的就是筛法家族中最著名、也最实用的两位成员埃拉托斯特尼筛法简称埃式筛法和欧拉筛法也叫线性筛法或欧式筛法。别看它们的目标都是找质数但背后的思想和效率却大有不同。埃式筛法历史久远思想直观是理解筛法的绝佳起点而欧式筛法则是在埃式筛法基础上的精妙优化将效率提升到了理论上的极致——线性时间复杂度。理解这两种算法不仅能让你在解决“求质数个数”、“判断大数是否为质数”这类问题时游刃有余更能深刻体会到算法设计中“空间换时间”、“避免重复计算”这些核心思想。无论是准备编程面试还是解决实际项目中的性能瓶颈这份知识都至关重要。2. 算法核心思想与原理对比2.1 埃拉托斯特尼筛法古老而直观的智慧埃式筛法的思想可以追溯到古希腊数学家埃拉托斯特尼。它的核心逻辑异常清晰甚至可以用一个生活场景来类比假设你要找出1到100之间所有的质数。首先你列出一张从2到100的表格。我们知道1不是质数所以从2开始。第一个数是2它是一个质数。但所有2的倍数4, 6, 8, …肯定都不是质数因为它们至少有一个因子2。于是你把表格中所有2的倍数全部“筛掉”标记为合数。接下来看下一个未被筛掉的数是3。3没有被2筛掉说明它不能被2整除因此3是质数。然后你把所有3的倍数6, 9, 12, …也筛掉。注意这里6已经被2筛过一次了但再筛一次也无妨。继续这个过程下一个未被筛掉的是54已被筛掉筛掉5的所有倍数然后是7筛掉7的倍数……以此类推。那么什么时候停止呢这是一个关键点。我们只需要筛选到√n即n的平方根为止。为什么因为如果某个数m是合数那么它一定可以分解为两个因子a和b且至少有一个因子小于等于√m。如果我们在筛选过程中已经把小于等于√n的所有质数的倍数都筛除了那么任何大于√n的合数其最小质因子必然已经在我们处理过的质数列表中因此这个合数肯定已经被它的最小质因子筛掉了。对于n100√10010所以我们只需要用2, 3, 5, 7这几个质数去筛一遍即可。最后所有未被标记的数就是1到100之间的全部质数。这个算法的代码实现也非常直观。通常我们会用一个布尔数组is_prime来表示每个数是否是质数初始假设所有数都是质数True然后遍历并标记合数为False。时间复杂度分析埃式筛法的时间复杂度是O(n log log n)。这个复杂度已经比O(n)差一点但比O(n log n)和O(n²)好得多。推导过程涉及一些数论知识简单理解就是每个数被标记为合数的次数大约是n除以它的质因子之和这个和收敛到一个与log log n相关的常数。对于n1,000,000log log n大约是一个很小的值因此效率非常高。空间复杂度需要一個大小为n1的布尔数组因此是O(n)。注意在具体实现时内层循环标记倍数可以从i*i开始而不是2*i。因为对于质数i像2*i,3*i, …,(i-1)*i这些数它们的最小质因子一定小于i所以在之前遍历更小的质数时就已经被筛掉了。从i*i开始标记可以避免一部分重复操作。2.2 欧拉筛法极致的线性优化埃式筛法已经很高效了但它有一个小瑕疵重复标记。比如合数12它会被质数2标记一次26又会被质数3标记一次34。当数据范围n极大时这种重复标记累积起来就是不小的开销。欧拉筛法的目标就是彻底消除这种重复确保每个合数只被它的最小质因子标记一次从而将时间复杂度降到严格的O(n)。欧拉筛法的核心思想需要仔细理解。它同样维护一个质数列表primes和一个布尔数组is_prime。但它的遍历方式很独特外层循环一个整数i从2遍历到n。如果i是质数is_prime[i]为True就把它加入质数列表primes。无论i是不是质数都用一个内层循环遍历当前已有的质数列表primes中的每个质数p。标记合数i * p为False。关键的一步如果i能被当前质数p整除即i % p 0则立即跳出内层循环。第5步是欧拉筛法的灵魂也是保证线性时间复杂度的关键。我们来分析一下为什么我们的目标是让每个合数N只被它的最小质因子min_p标记。在算法中合数N是在外层循环i N / min_p时被内层循环中的p min_p标记的即N i * min_p。如果i能被p整除即i % p 0那么i可以写成p * k。此时对于下一个质数p_next比p大我们要标记的合数是i * p_next p * k * p_next。注意这个合数p * k * p_next的最小质因子是p而不是p_next。如果我们现在用p_next把它标记了那么在未来当外层循环i k * p_next时这个数还会被它的最小质因子p再标记一次因为i * p k * p_next * p这就造成了重复。因此当发现i % p 0时为了保证后续的合数i * p_next能在未来被其最小质因子p正确标记现在就必须停止用更大的质数p_next去标记它。所以要break掉内层循环。通过这个精巧的break条件欧拉筛法确保了每个合数只被筛一次。它的时间复杂度是O(n)虽然常数项可能比埃式筛法大一点但在n极大例如上亿时线性复杂度的优势会非常明显。空间复杂度同样需要 O(n) 的布尔数组以及一个存储质数的列表质数个数约为n / ln(n)所以额外空间也是 O(n) 级别。3. 算法实现与代码细节解析理解了原理我们来看看如何用代码实现它们。这里我会用Python来演示因为其语法清晰易于理解。两种算法的核心代码都不长但细节决定成败。3.1 埃式筛法的标准实现与优化我们先来看最基础的埃式筛法实现def eratosthenes_sieve(n): 埃拉托斯特尼筛法返回小于n的所有质数列表。 if n 2: return [] is_prime [True] * n # 创建n个元素的列表初始全为True is_prime[0] is_prime[1] False # 0和1不是质数 for i in range(2, int(n ** 0.5) 1): # 只需遍历到sqrt(n) if is_prime[i]: # 如果i是质数 # 从i*i开始步长为i标记所有i的倍数为False for j in range(i * i, n, i): is_prime[j] False # 收集所有is_prime[i]为True的i primes [i for i in range(2, n) if is_prime[i]] return primes代码要点解析初始化is_prime列表长度为n索引对应数字本身。is_prime[0]和is_prime[1]直接设为False。外层循环范围for i in range(2, int(n ** 0.5) 1)。这是算法的关键优化如前所述只需要检查到√n。内层循环起点for j in range(i * i, n, i)。从i*i开始标记而不是2*i。这是另一个重要优化。为什么可以从i*i开始因为对于任意小于i的倍数k*i(k i)这个数k*i一定有一个比i小的质因子就是k的某个质因子所以在之前遍历到那个更小的质因子时k*i已经被标记过了。例如i5时10(2*5)在i2时被标记15(3*5)在i3时被标记所以我们从25(5*5)开始标记即可。结果收集使用列表推导式[i for i in range(2, n) if is_prime[i]]来生成最终的质数列表非常简洁。一个常见的“踩坑点”在判断外层循环终点时一定要int(n ** 0.5) 1。因为range是左闭右开的int(n**0.5)可能因为浮点数精度问题略小于实际平方根加1能确保覆盖。更稳妥的写法是i * i n作为循环条件。3.2 欧拉筛法的精妙实现欧拉筛法的实现需要仔细处理内层循环的break条件。def euler_sieve(n): 欧拉筛法线性筛法返回小于n的所有质数列表。 if n 2: return [] is_prime [True] * n primes [] # 用于存储找到的质数 is_prime[0] is_prime[1] False for i in range(2, n): if is_prime[i]: primes.append(i) # i是质数加入列表 # 遍历当前已找到的质数列表 for p in primes: if i * p n: # 如果乘积超过范围提前结束内循环 break is_prime[i * p] False # 标记合数 i * p if i % p 0: # *** 核心保证每个合数只被最小质因子筛掉 *** break return primes代码要点解析双重循环结构外层循环i从2到n-1注意这里不是到√n。因为欧拉筛法需要遍历每个数来判断和标记。质数判断与收集如果is_prime[i]为True则i是质数将其加入primes列表。这个判断发生在遍历质数列表primes之前顺序很重要。内层循环遍历质数列表for p in primes:。这里遍历的是动态增长的质数列表。提前终止条件1if i * p n: break。当要标记的合数i*p已经超出我们的范围n时后面的p更大乘积肯定也超出范围所以直接跳出内层循环。标记合数is_prime[i * p] False。核心终止条件2if i % p 0: break。这就是欧拉筛法的精髓。一旦发现i能被当前质数p整除就立即停止用更大的质数去标记。这确保了合数i * p_next会在未来被其最小质因子即p标记。实操心得在实现欧拉筛时最容易出错的就是内层循环两个break条件的顺序。必须先判断i*p n来防止数组越界然后再进行标记和i % p 0的判断。如果顺序反了当i*p n时可能会先执行i % p 0的判断并break但此时is_prime[i*p]的索引已经越界会导致程序崩溃。3.3 两种算法性能的直观对比光说不练假把式我们写个简单的测试来感受一下两者的效率差异import time def test_sieve_performance(n): print(f测试范围: 1 到 {n}) start time.time() primes_e eratosthenes_sieve(n) time_e time.time() - start print(f埃式筛法: 找到 {len(primes_e)} 个质数耗时 {time_e:.4f} 秒) start time.time() primes_o euler_sieve(n) time_o time.time() - start print(f欧拉筛法: 找到 {len(primes_o)} 个质数耗时 {time_o:.4f} 秒) # 验证结果是否一致 print(f结果一致: {primes_e primes_o}) if __name__ __main__: test_sieve_performance(1000000) # 测试100万在我的电脑上运行结果大致如下测试范围: 1 到 1000000 埃式筛法: 找到 78498 个质数耗时 0.0350 秒 欧拉筛法: 找到 78498 个质数耗时 0.0550 秒 结果一致: True咦看起来在100万这个量级埃式筛法0.035秒反而比欧拉筛法0.055秒更快这似乎和“线性复杂度更优”的理论不符。原因在于常数项。欧拉筛法虽然每个合数只标记一次但它有更多的逻辑判断两个if条件尤其是取模运算i % p比较耗时并且内层循环的遍历次数和质数个数相关。而埃式筛法的内层循环虽然可能重复标记但它的操作简单的加法j i和数组赋值非常快。那么欧拉筛法的优势在哪里呢在于更大的数据范围和需要质数列表的场景。当我们把n扩大到5000万或1亿测试范围: 1 到 50000000 埃式筛法: 找到 3001134 个质数耗时 1.85 秒 欧拉筛法: 找到 3001134 个质数耗时 1.52 秒此时欧拉筛法开始反超。当n趋向于无穷大时O(n)的线性增长最终会战胜O(n log log n)。此外欧拉筛法在运行过程中就自然地生成了有序的质数列表primes如果需要频繁按顺序访问质数这个列表是现成的。而埃式筛法最后需要遍历整个布尔数组来收集质数。4. 高级应用、变体与问题排查掌握了两种筛法的基本实现我们可以看看它们能解决哪些实际问题以及一些常见的变体和优化技巧。4.1 解决经典算法问题筛法不仅仅是“求质数列表”它可以作为核心工具解决许多衍生问题。问题一计数质数LeetCode 204题目要求计算小于非负整数n的质数的数量。这正是筛法的用武之地。我们不需要返回完整的质数列表只需要在筛的过程中计数即可。埃式筛法的计数版本效率很高。def count_primes_eratosthenes(n): if n 3: # 小于3的数里只有2是质数 return 0 if n 2 else 1 is_prime [True] * n count n // 2 # 初始假设所有奇数都是质数除了2偶数肯定不是除了2 is_prime[0] is_prime[1] False # 只遍历奇数因为偶数肯定不是质数除了2 for i in range(3, int(n ** 0.5) 1, 2): if is_prime[i]: # 从i*i开始步长为2*i因为i是奇数i*i也是奇数但i*i i是偶数无需标记 # 只标记奇数的倍数偶数倍已经在初始计数时排除了 step i * 2 for j in range(i * i, n, step): if is_prime[j]: is_prime[j] False count - 1 return count这个版本做了进一步优化初始时排除所有偶数只处理奇数将数组大小和计算量几乎减半。问题二判断大数是否为质数结合筛法对于单个非常大的数比如几十位筛法不适用需要用米勒-拉宾素性测试等概率算法。但对于“判断一个范围内的数是否都是质数”或“预处理质数表用于快速查询”筛法是首选。我们可以先用筛法生成一个sqrt(max_num)范围内的质数表然后用这些质数去试除目标大数这比纯试除法快得多。4.2 埃式筛法的常见优化变体除了从i*i开始和只遍历奇数还有更激进的优化分段筛法当n极大例如10^12无法在内存中分配大小为n的数组。分段筛法将区间[0, n)分成若干个小段每次只将当前段加载到内存中筛选。需要预先筛出√n以内的质数然后用这些小质数去筛选每一个内存段。位图筛法用比特位bit而不是字节byte来存储一个数是否是质数。一个bool在Python中通常占1个字节8比特而用位图如Python的int类型按位操作或bitarray库可以用1个比特表示内存占用减少为1/8。这对于内存敏感的超大规模筛选至关重要。只筛6k±1形式除了2和3所有质数都位于6的倍数两侧即形式为6k-1或6k1。可以利用这个性质进一步减少初始待筛选的候选数。4.3 欧拉筛法的扩展应用欧拉筛法的核心思想——用最小质因子筛选——可以推广到计算一些积性函数的前缀和。计算欧拉函数φ(n)的前缀和欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的数目。它是一个积性函数。我们可以在欧拉筛的过程中同步计算出每个数的φ值。def euler_phi_sieve(n): 使用欧拉筛法思想计算1到n每个数的欧拉函数值。 phi list(range(n 1)) # phi[i] 初始化为i primes [] is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, n 1): if is_prime[i]: primes.append(i) phi[i] i - 1 # 质数i的欧拉函数值为i-1 for p in primes: if i * p n: break is_prime[i * p] False if i % p 0: # i 和 p 不互质i*p 的最小质因子是p phi[i * p] phi[i] * p break else: # i 和 p 互质利用积性函数性质 phi[i * p] phi[i] * phi[p] return phi类似地还可以计算莫比乌斯函数μ(n)、约数个数d(n)、约数和σ(n)等数论函数的前缀和。这是欧拉筛法在算法竞赛和数论研究中的一个强大应用。4.4 常见问题与调试技巧在实现筛法时可能会遇到一些典型问题结果错误漏掉质数或多出合数检查边界数组大小是n还是n1循环的起止点是否正确特别是埃式筛法外层循环的终点int(n**0.5)1。检查初始化是否正确地排除了0和1is_prime[0]和is_prime[1]是否设为False。欧拉筛法的break条件确保if i % p 0: break这行代码存在且位置正确在标记合数之后。程序运行缓慢埃式筛法确认内层循环是否从i*i开始。对于超大的n考虑使用只筛奇数的优化甚至分段筛法。欧拉筛法它的常数较大在n较小10^6时可能不如优化后的埃式筛法快。这是正常的。语言特性在Python中纯循环操作较慢。对于性能要求极高的场景如n10^7可以考虑使用NumPy库的向量化操作来实现埃式筛法或者用PyPy解释器运行对循环有JIT优化甚至用C重写核心部分。内存不足当n很大时一个长度为n的布尔数组可能占用几百MB甚至上GB内存。解决方案使用位图如前所述用bitarray或手动位运算压缩内存。使用分段筛法只将当前段加载到内存。使用bytearray代替list在Python中bytearray比list更节省内存。欧拉筛法理解难点为什么i要从2遍历到n因为每个合数N都需要在i N / min_p时被筛掉i可能很大。内层循环为什么既要遍历质数列表因为我们要用当前数i乘以每一个已知质数p来生成合数并保证p是i*p的最小质因子。i % p 0时 break 的深层原因可以这样记忆——我们要维持一个承诺每个合数只被它的最小质因子筛掉。当i能被p整除时i本身已经含有质因子p。对于下一个更大的质数p_next合数i * p_next的最小质因子应该是p因为i里已经有p了而不是p_next。如果我们现在用p_next筛了它就破坏了“最小质因子”的承诺未来这个数会被p再筛一次。所以必须停止。最后分享一个我个人的调试习惯在实现完筛法后先用小范围的n比如30手动模拟运行打印出每一步i、p、被标记的合数以及质数列表的变化。这对于理解欧拉筛法那个关键的break条件尤其有效。眼见为实跟踪一遍数据流比看十遍原理说明都管用。算法学习尤其是这种精巧的算法切忌死记硬背代码一定要把背后的“为什么”想明白这样才能在遇到变种问题时灵活应用。