1. 从“暴力枚举”到“筛法”为什么我们需要更聪明的算法在编程和算法学习的路上判断一个数是不是质数几乎是每个人都会遇到的第一个“坎”。新手最直观的想法就是“暴力枚举”对于一个给定的正整数 n从 2 开始一直试除到 n-1如果中间有任何数能整除 n那 n 就不是质数。这个方法简单直接但效率极低。当 n 稍微大一点比如到 10^6 这个量级这种方法的计算量就变得难以接受。更进一步的优化是我们只需要试除到 √n 就可以了。因为如果 n 有一个大于 √n 的因子 a那么它必然对应一个小于 √n 的因子 b因为 a * b n。这个优化将时间复杂度从 O(n) 降到了 O(√n)对于单个数的判断来说已经是教科书级的优化了。但是如果我们的问题变了“请找出 1 到 1000 万之间的所有质数”。这时即使对每个数都用 O(√n) 的方法判断总计算量依然是天文数字。我们需要一种能“批量”生产质数的方法而不是一个个地“检验”。这就是“筛法”粉墨登场的时刻。筛法的核心思想不是“判断”而是“排除”或“筛选”。它像一个精密的过滤器通过一套既定的规则主动地将合数非质数标记出来最后剩下的就是质数。这种思路的转变带来了效率的飞跃。今天我们要深入探讨的就是筛法家族中最著名、也最基础的两个成员埃拉托斯特尼筛法简称埃式筛法和欧拉筛法也称线性筛法或欧式筛法。它们不仅仅是找出质数的工具更是理解算法优化、空间换时间、以及数论基本性质的绝佳范例。无论你是正在准备算法面试还是对程序效率有极致追求吃透这两种筛法都大有裨益。2. 埃拉托斯特尼筛法古老而经典的智慧埃拉托斯特尼是古希腊的数学家他在公元前就提出了这个算法其简洁与高效令人惊叹。它的原理可以用一个生活中的场景来类比假设你有一张写满了从2开始连续整数的表格你的目标是找出所有的质数。2.1 核心原理与步骤拆解埃式筛法的操作流程非常直观建立初始列表创建一个布尔数组isPrime[0...n]初始时假设所有大于等于2的数都是质数设为true。从第一个质数开始从p 2开始我们知道2是最小的质数。标记倍数如果isPrime[p]是true那么对于所有k p * 2, p * 3, p * 4, ...且k n的数将isPrime[k]标记为false。因为这些数都是p的倍数所以它们一定是合数。寻找下一个质数找到下一个大于p且isPrime值仍为true的数这个数就是下一个质数。重复步骤3。终止条件当p * p n时就可以停止了。因为所有小于等于 n 的合数其最小的质因子一定小于等于 √n。在标记完所有小于等于 √n 的质数的倍数后剩下的未被标记的数就都是质数了。让我们以找出 30 以内的质数为例手动模拟这个过程初始列表2到30都标记为质数。p2标记 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 为合数。下一个p3未被标记标记 9, 15, 21, 27 为合数。注意6, 12, 18等已经是合数但重复标记不影响结果。下一个p5未被标记标记 25 为合数。下一个p7未被标记7*749 30停止。此时列表中未被标记的数2, 3, 5, 7, 11, 13, 17, 19, 23, 29。这些就是30以内的所有质数。2.2 代码实现与时间复杂度分析基于上述原理一个标准的埃式筛法实现如下以Python为例def eratosthenes_sieve(n): 返回小于等于n的所有质数列表。 if n 2: return [] # 初始化布尔数组索引代表数字True表示是质数假设 is_prime [True] * (n 1) is_prime[0] is_prime[1] False # 0和1不是质数 # 只需遍历到 sqrt(n) for i in range(2, int(n ** 0.5) 1): if is_prime[i]: # 如果i是质数 # 从 i*i 开始标记因为更小的倍数如 i*2, i*3... 已经被更小的质数标记过了 for j in range(i * i, n 1, i): is_prime[j] False # 收集所有质数 primes [i for i in range(2, n 1) if is_prime[i]] return primes # 示例找出100以内的质数 print(eratosthenes_sieve(100))时间复杂度分析埃式筛法的时间复杂度是O(n log log n)。这个复杂度已经非常优秀远优于对每个数单独进行 O(√n) 判断的 O(n√n)。log log n是一个增长极其缓慢的函数即使 n 是 10^9log log n也大约只有 5。因此埃式筛法在实践中有很高的效率。空间复杂度需要 O(n) 的布尔数组来存储标记信息。2.3 埃式筛法的优势与局限性优势原理简单逻辑清晰极易理解和实现是学习筛法的完美起点。效率足够对于绝大多数需要一次性预处理质数表的场景如竞赛编程中 n ≤ 10^7O(n log log n) 的复杂度完全够用且常数很小运行速度快。易于优化存在一些经典的优化技巧如只筛选奇数、使用位图bitset压缩空间等能进一步提升性能。局限性核心缺陷重复标记这是埃式筛法最根本的效率瓶颈。一个合数可能被多个质因子重复标记。例如合数 30 2 * 15 3 * 10 5 * 6它会被质数2、3、5各标记一次。当 n 很大时这种重复劳动会累积成可观的开销。非线性时间复杂度虽然 O(n log log n) 很好但理论上存在更优的 O(n) 算法。注意在代码实现中内层循环从i * i开始是一个关键优化。为什么不是从2 * i开始因为对于质数i2*i,3*i, ...,(i-1)*i这些数它们的最小质因子一定小于i所以在之前遍历到更小的质数时就已经被标记过了。从i*i开始可以避免这部分重复工作。3. 欧拉筛法追求极致的线性效率为了克服埃式筛法“重复标记”的缺陷欧拉筛法线性筛法应运而生。它的核心目标是确保每个合数只被其最小的质因子标记一次从而达到理论上的 O(n) 时间复杂度。3.1 算法原理如何保证只标记一次欧拉筛法同样维护一个质数表primes和一个状态数组is_prime。但其运行逻辑更为精巧外层遍历所有数从 2 到 n遍历每一个整数i。维护质数表如果当前数i是质数is_prime[i]为真则将其加入质数表primes。内层遍历已知质数无论i是否是质数都遍历当前已找到的质数表primes中的每个质数p。标记合数与关键中断计算合数n i * p。如果n超过上限则跳出内层循环。标记is_prime[n] False。最关键的一步如果i能被当前质数p整除即i % p 0则在标记完n i * p后立即跳出内层循环。为什么这个中断条件如此重要这正是保证每个合数只被标记一次的灵魂所在。让我们来推演一下假设我们要标记合数x。设x的最小质因子是p_min。那么x一定可以表示为x i * p_min其中i x / p_min。 在欧拉筛法的运行过程中当外层循环i取到x / p_min这个值时内层循环会遍历质数表。当遍历到质数p_min时我们会标记x i * p_min。如果此时i已经包含了质因子p_min即i % p_min 0那么对于后续比p_min更大的质数p‘如果我们继续标记i * p’这个合数的最小质因子就不是p‘了而是p_min。这会导致重复标记。因此必须中断。如果i不包含质因子p_min那么p_min就是x的最小质因子这次标记是唯一且正确的。通过这个机制每个合数x都会在其最小质因子p_min与对应的i x / p_min相遇时被标记一次且仅此一次。3.2 代码实现与逐行解析def euler_sieve(n): 返回小于等于n的所有质数列表欧拉筛法/线性筛法。 is_prime [True] * (n 1) primes [] # 用于存储找到的质数 for i in range(2, n 1): if is_prime[i]: primes.append(i) # 步骤1i是质数加入列表 # 步骤2遍历当前已知的质数 for p in primes: composite i * p if composite n: # 超过范围跳出 break is_prime[composite] False # 标记合数 if i % p 0: # ***核心中断条件*** break return primes # 示例 print(euler_sieve(100))让我们跟踪一段执行过程以理解其精妙。假设n20。i2: 是质数primes[2]。内层循环p2,composite420标记4为合数。判断2 % 2 0中断。i3: 是质数primes[2,3]。内层循环p2:composite6标记6。3 % 2 ! 0继续。p3:composite9标记9。3 % 3 0中断。i4: 不是质数已标记。primes[2,3]。内层循环p2:composite8标记8。4 % 2 0中断。注意没有用p3去标记12因为12的最小质因子是2它会在i6时被p2标记i5: 是质数primes[2,3,5]。内层循环p2:composite10标记10。5 % 2 !0继续。p3:composite15标记15。5 % 3 !0继续。p5:composite2520跳出循环。i6: 不是质数。primes[2,3,5]。内层循环p2:composite12标记12。6 % 2 0中断。没有标记18因为18的最小质因子是2将在i9时被p2标记这里需要仔细分析实际上18 9 * 2当i9时p2会标记18。因为9的最小质因子是3但p2小于3所以i9时p2仍会参与循环并标记18然后遇到9 % 2 ! 0继续再用p3标记27时中断。所以18被正确标记了一次。通过这个过程可以看到每个合数如12都只被标记了一次。3.3 欧拉筛法的优势与代价优势理论复杂度最优严格 O(n) 的时间复杂度。在处理极大范围的质数筛选时例如 n 10^7其优势开始显现。无重复计算每个合数只被访问一次消除了埃式筛法的冗余操作。代价与注意事项逻辑复杂度高理解其正确性特别是中断条件比埃式筛法困难得多。常数可能更大虽然理论复杂度低但由于其内层循环的逻辑判断求模运算i % p相对昂贵在n不是特别大比如 n 10^7时其实际运行速度可能不如高度优化过的埃式筛法如仅处理奇数的位运算版。对缓存不友好内层循环需要跳跃式访问primes列表和is_prime数组可能不如埃式筛法的连续内存访问模式高效。实操心得在算法竞赛或日常编程中如果题目给定的n在 10^7 量级以下优先使用埃式筛法。它代码简单不易出错且经过位图优化后速度飞快。只有当题目明确要求 O(n) 复杂度或者n的范围极大如 10^8你才需要考虑实现欧拉筛法。在面试中能清晰阐述欧拉筛法的原理通常比写出无 bug 的代码更能体现你的理解深度。4. 性能实测与场景选择指南理论分析很重要但实际运行速度才是最终标准。我们设计一个简单的测试来对比两种算法。import time def test_performance(n): print(f测试范围: 1 - {n}) start time.time() primes_eratosthenes eratosthenes_sieve(n) time_eratosthenes time.time() - start print(f埃式筛法 耗时: {time_eratosthenes:.4f} 秒找到 {len(primes_eratosthenes)} 个质数) start time.time() primes_euler euler_sieve(n) time_euler time.time() - start print(f欧拉筛法 耗时: {time_euler:.4f} 秒找到 {len(primes_euler)} 个质数) # 验证结果一致性 assert primes_eratosthenes primes_euler, “结果不一致” print(结果验证: 一致) print(- * 40) if __name__ __main__: test_performance(10**6) # 100万 test_performance(5*10**6) # 500万 test_performance(10**7) # 1000万在我的开发环境普通笔记本下可能得到类似如下的结果具体时间因机器而异测试范围: 1 - 1000000 埃式筛法 耗时: 0.0352 秒找到 78498 个质数 欧拉筛法 耗时: 0.0481 秒找到 78498 个质数 结果验证: 一致 ---------------------------------------- 测试范围: 1 - 5000000 埃式筛法 耗时: 0.2153 秒找到 348513 个质数 欧拉筛法 耗时: 0.2810 秒找到 348513 个质数 结果验证: 一致 ---------------------------------------- 测试范围: 1 - 10000000 埃式筛法 耗时: 0.4521 秒找到 664579 个质数 欧拉筛法 耗时: 0.5785 秒找到 664579 个质数 结果验证: 一致结果分析在千万量级以下基础的埃式筛法实现反而比欧拉筛法更快。这是因为欧拉筛法每次迭代中的求模运算i % p带来了不小的常数开销。而埃式筛法的内层循环是简单的加法j i现代CPU对此优化得非常好。那么欧拉筛法的优势在哪里复杂度上限当n继续增大到亿级甚至十亿级时O(n) 和 O(n log log n) 的差距会逐渐体现出来。欧拉筛法的增长更线性。衍生应用欧拉筛法的框架极其强大。它不仅能筛质数还能在筛的过程中以 O(n) 的复杂度同步计算出许多数论函数例如每个数的最小质因子。欧拉函数 φ(n)。莫比乌斯函数 μ(n)。除数函数等。 这是埃式筛法难以高效完成的。例如要计算1到n每个数的欧拉函数使用欧拉筛法可以在 O(n) 内完成而其他方法则复杂得多。4.1 如何选择决策流程图面对一个问题你可以遵循以下思路选择是否需要一次性筛选出 1~N 的所有质数 | |-- 否 -- 使用单个数的判定算法试除法Miller-Rabin等。 | |-- 是 | |-- N 10^7且只需质数列表 | | | |-- 是 -- 使用 **优化后的埃式筛法**推荐仅奇数位图。 | | | |-- 否 -- 除了质数是否还需要每个数的最小质因子、欧拉函数等附加信息 | | | |-- 是 -- 使用 **欧拉筛法**。 | | | |-- 否 -- 继续判断。 | |-- N 10^7或对时间复杂度有严格O(n)要求 | |-- 是 -- 使用 **欧拉筛法**。 | |-- 否 -- 仍可优先尝试优化版埃式筛法。4.2 埃式筛法的经典优化技巧如果你选择了埃式筛法这些优化可以让你如虎添翼仅处理奇数除了2以外所有偶数都不是质数。我们可以只初始化一个表示奇数的布尔数组大小减半内存和计算量都减半。使用位图Bitset用 Python 的int或bytearray或者 C 的std::bitsetJava 的BitSet来存储标记。一个比特位代表一个数的状态能将空间消耗降低到原来的 1/8 甚至更多。分段筛选当n极大无法一次性分配O(n)内存时可以将区间分段每次只筛一段。这需要更复杂的边界处理但能突破内存限制。这里给出一个 Python 的“仅奇数”优化版埃式筛法示例def optimized_eratosthenes_sieve(n): 优化版埃式筛法仅处理奇数使用半长数组。 if n 2: return [] if n 2: return [2] # is_prime[i] 代表数字 (2*i 3) 是否为质数 limit (n - 1) // 2 is_prime [True] * (limit 1) primes [2] # 先把2加入质数表 # 只遍历奇数 for i in range(limit 1): if is_prime[i]: p 2 * i 3 # 当前代表的实际质数 primes.append(p) # 从 p*p 开始标记注意步长为 2*p (因为只关心奇数倍) start (p * p - 3) // 2 if start limit: for j in range(start, limit 1, p): is_prime[j] False return primes这个版本在处理大数时速度和内存表现都远优于基础版本。5. 从筛法到更广阔的数论世界理解埃式筛法和欧拉筛法不仅仅是掌握了两个找质数的工具。它们背后蕴含的思想是打开数论和算法优化大门的一把钥匙。埃式筛法教会我们“以空间换时间”和“批量处理”的思想。通过预分配一个状态数组我们避免了大量重复的、独立的计算。这种预处理思想在动态规划、前缀和、树状数组等算法中随处可见。欧拉筛法则更深入地揭示了数的本质结构——每个合数都有唯一的最小质因子分解。它通过精巧的循环控制确保了每个数只被其“最小质因子”访问一次。这种“每个元素只处理一次”的思想是很多线性时间算法的核心比如拓扑排序、KMP算法的一部分。在实际应用中质数筛选是许多高级算法的基础模块质因数分解先筛出一定范围内的质数可以快速对一个数进行分解。RSA加密算法需要生成大质数高效的质数测试和筛选是关键步骤。解决与公约数、公倍数相关的问题常常需要利用质数分布的性质。各类数论函数的前缀和计算如欧拉函数前缀和、莫比乌斯函数前缀和其高效计算都离不开线性筛。最后再分享一个小技巧在面试或竞赛中如果被问到质数相关问题可以先从最基础的试除法讲起然后自然引出其效率瓶颈再提出埃式筛法作为优化并分析其复杂度。如果面试官追问再深入探讨欧拉筛法的原理和优势。这样的回答层次分明能很好地展示你的知识体系。自己实现时如果时间允许可以先写一个清晰的埃式筛法并提及“还有更优的线性筛法但此处出于时间考虑使用埃式筛”。这比直接写一个可能有 bug 的欧拉筛法要稳妥得多。毕竟在绝大多数场景下正确且高效的埃式筛法已经足够出色。