1. 项目概述为什么我们需要素数筛法在编程和算法竞赛中判断一个数是否为素数或者找出一定范围内的所有素数是一个经典且高频的问题。新手可能会从最直观的“试除法”入手即对于一个数 n从 2 遍历到 √n检查是否能被整除。这种方法对于单个数的判断尚可但一旦问题变成“找出 1 到 100 万之间的所有素数”其时间复杂度 O(n√n) 就完全无法接受了计算量会大到程序几乎无法在合理时间内完成。这正是素数筛法Sieve大显身手的地方。筛法的核心思想不是去“判断”每个数而是去“标记”和“排除”合数从而高效地“筛”出素数。今天我们就来深入拆解两种最经典、应用最广的筛法埃拉托斯特尼筛法简称埃氏筛和欧拉筛也称线性筛。我会结合自己多年刷题和项目开发的经验不仅讲清楚原理和代码更会分享在实际应用中如何选择、优化以及避坑让你彻底掌握这两种利器。2. 算法核心思路与原理对比理解两种筛法的根本差异是正确选择和使用的关键。它们的目标一致但实现路径和效率截然不同。2.1 埃氏筛直观高效的“批量标记”埃氏筛的思路非常直观像用筛子过滤沙子。我们假设一开始所有数都是“素数候选”。从最小的素数 2 开始将其所有的倍数4, 6, 8, 10...标记为合数。然后找到下一个未被标记的数此时是3它一定是素数因为所有小于它的数的倍数都已检查过再将 3 的所有倍数标记为合数。如此反复直到处理完所有数。其核心操作可以概括为对于一个素数p标记p * 2,p * 3,p * 4, ... 为合数。为什么有效因为任何一个合数n都可以表示为n p * qp ≤ q。当我们用最小的素因子p去筛选时n必然会在遍历到p时被标记为合数。这就保证了所有合数都会被筛掉剩下的就是素数。埃氏筛的复杂度其时间复杂度为 O(n log log n)。这个复杂度已经非常优秀对于 n 10^6一百万级别的问题绰绰有余代码也极其简洁是许多场景下的首选。2.2 欧拉筛追求极致的“线性筛”埃氏筛虽然高效但它有一个明显的“浪费”一个合数可能会被它的多个素因子重复标记。例如合数 12 2 * 6 3 * 4在埃氏筛中它既会被素数 2 标记26也会被素数 3 标记34。当数据范围n极大例如 10^7 或更大时这种重复操作累积起来会成为性能瓶颈。欧拉筛的诞生就是为了解决这个问题确保每个合数只被其最小的素因子标记一次从而达到理论上的线性时间复杂度 O(n)。这是以略微复杂的逻辑为代价换来的极致效率。欧拉筛的核心机制维护一个素数列表primes。从小到大遍历每个整数i。对于每个i用当前已知的素数primes[j]去尝试标记合数i * primes[j]。关键终止条件当i % primes[j] 0时立即停止内层循环。为什么这个终止条件如此重要这正是保证每个合数只被筛一次的精髓所在。假设i % primes[j] 0即i primes[j] * k。那么对于下一个素数primes[j1]要标记的合数是i * primes[j1] primes[j] * k * primes[j1]。你会发现这个合数的最小素因子是primes[j]它本应在未来当i增长到k * primes[j1]时用primes[j]这个更小的素因子去标记。如果现在用primes[j1]标记了就造成了重复。因此此时必须跳出循环。3. 代码实现与逐行解析理解了原理我们来看代码。我会提供 Python 和 C 两种常见语言的实现并加入详细注释和我的调试心得。3.1 埃氏筛的实现与优化技巧基础版本 Python 实现def sieve_eratosthenes(n): 埃氏筛法返回小于 n 的所有素数列表。 is_prime [True] * (n) # 初始化标记数组假设所有数都是素数 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, ..., i*(i-1) 已经被更小的素数标记过了 for j in range(i * i, n, i): is_prime[j] False # 收集所有素数 primes [i for i in range(2, n) if is_prime[i]] return primes # 示例找出 100 以内的素数 primes sieve_eratosthenes(100) print(primes[:20]) # 输出前20个素数关键点解析与我的踩坑经验is_prime数组大小通常创建长度为n的数组下标对应数字本身。is_prime[i]为True表示i是素数。注意这个数组通常不包含n本身函数返回的是小于n的素数。外层循环终止条件int(n ** 0.5) 1这是最重要的优化之一。因为任何合数n必有一个因子 ≤ √n。所以如果一个数没有被 ≤ √n 的素数筛掉那它一定是素数。这大大减少了外层循环次数。内层循环起始点i * i这是另一个关键优化。思考一下对于素数i它的倍数i*2,i*3, ...,i*(i-1)的最小素因子一定小于i例如i*2的最小素因子是 2。这些数在之前遍历更小的素数时比如 2, 3, ...就已经被标记过了。从i*i开始标记避免了大量重复工作。内存与速度的权衡基础版本使用布尔列表内存占用尚可。对于极大的n如 10^8可以考虑使用bytearray或bitset在C中来进一步压缩内存这对缓存友好能显著提升速度。C 优化版本使用 vector 特化#include iostream #include vector using namespace std; vectorint sieveEratosthenes(int n) { // vectorbool 通常被特化以节省空间每个元素占1 bit vectorbool is_prime(n, true); is_prime[0] is_prime[1] false; for (int i 2; i * i n; i) { // 用 i*i n 代替 sqrt计算更快 if (is_prime[i]) { // 注意这里 j 可能会溢出 int所以用 long long 或提前判断 for (int j i * i; j n; j i) { is_prime[j] false; } } } vectorint primes; for (int i 2; i n; i) { if (is_prime[i]) primes.push_back(i); } return primes; }注意C中vectorbool的j i操作当n很大时i*i可能超出int范围导致溢出成为负数从而引发段错误或死循环。这是埃氏筛一个经典的坑。安全的写法是内层循环变量j使用long long类型或者增加判断if (i n / i)。3.2 欧拉筛的实现与细节剖析欧拉筛的逻辑稍复杂但代码结构非常规整。Python 实现def sieve_euler(n): 欧拉筛线性筛返回小于 n 的所有素数列表。 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 是素数加入列表 # 遍历已知素数 primes[j] for j in range(len(primes)): composite i * primes[j] if composite n: # 超出范围中断 break is_prime[composite] False # 标记合数 # **核心如果 i 能被当前素数整除则跳出循环** if i % primes[j] 0: break return primes # 示例 primes_linear sieve_euler(100) print(primes_linear[:20])C 实现#include iostream #include vector using namespace std; vectorint sieveEuler(int n) { vectorbool is_prime(n, true); vectorint primes; is_prime[0] is_prime[1] false; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); } // 用已知的素数 primes[j] 去筛 for (int j 0; j primes.size(); j) { long long composite 1LL * i * primes[j]; // 防止溢出 if (composite n) break; is_prime[composite] false; // 核心终止条件 if (i % primes[j] 0) break; } } return primes; }逐行解析与深度思考外层循环for i in range(2, n)注意这里i是遍历每一个数而不仅仅是素数。i扮演了两个角色一是它本身可能是素数if is_prime[i]分支二是作为“乘数”与已知素数结合来生成新的合数。if is_prime[i]: primes.append(i)如果i没有被之前的素数筛掉那么它一定是素数。这是因为欧拉筛的标记过程保证了所有合数都会被正确标记。内层循环for j in range(len(primes)):用当前数i去乘以每一个已知的素数primes[j]从而标记合数i * primes[j]。if composite n: break简单的边界检查防止数组越界。is_prime[composite] false执行标记。if i % primes[j] 0: break灵魂所在。如前所述这保证了composite只被其最小素因子primes[j]标记一次。理解这一点就理解了欧拉筛。一个具体的例子来验证假设n20当前i4已知素数primes [2, 3]。j0:composite 4*28标记8因为4%20跳出循环。为什么不让j1继续如果继续composite 4*312会标记12。但12的最小素因子是2它本应在i6(6*2) 时被标记。现在标记就重复了。所以必须跳出。4. 性能实测与场景选择指南理论说了很多是骡子是马拉出来溜溜。我写了一个简单的测试脚本来对比两种筛法在不同数据规模下的表现。import time import matplotlib.pyplot as plt def test_performance(): test_cases [10**4, 10**5, 5*10**5, 10**6, 5*10**6] # 测试规模 times_eratosthenes [] times_euler [] for n in test_cases: # 测试埃氏筛 start time.perf_counter() sieve_eratosthenes(n) end time.perf_counter() times_eratosthenes.append(end - start) # 测试欧拉筛 start time.perf_counter() sieve_euler(n) end time.perf_counter() times_euler.append(end - start) print(fn{n:8d}: 埃氏筛 {end-start:.4f}s, 欧拉筛 {times_euler[-1]:.4f}s) # 绘制对比图此处省略绘图代码实际可展示 # 通常结果在 n 较小时如1e6两者差距不大埃氏筛可能因代码简单更快。 # 当 n 很大时如5e6欧拉筛的线性优势开始明显体现。 if __name__ __main__: test_performance()根据我的实测经验选择建议如下场景推荐算法理由一般性编程问题/竞赛 (n ≤ 10^6)埃氏筛代码极其简洁不易写错O(n log log n) 复杂度完全够用且常数因子小实际运行往往很快。需要极高性能n 非常大 (10^7 ~ 10^8)欧拉筛线性复杂度 O(n) 在巨大数据量下优势无可比拟内存访问模式也更连续。需要频繁查询区间素数状态埃氏筛一次筛出整个is_prime布尔数组后续任何查询都是 O(1) 的。欧拉筛的primes列表二分查找是 O(log n)。内存极度受限埃氏筛 bitset 优化埃氏筛的is_prime数组可以用位压缩如 Pythonbitarray Cbitset内存占用远小于欧拉筛需要同时维护的is_prime数组和primes列表。理解算法原理与教学先埃氏后欧拉埃氏筛直观易懂是理解筛法思想的绝佳起点。理解了它的不足才能更好地欣赏欧拉筛的精妙。个人心得在绝大多数面试、笔试和日常开发中埃氏筛完全足够。它的代码简单到几乎可以默写不容易出错。除非题目明确要求线性复杂度或者你在处理天文数字级别的数据例如密码学相关应用否则优先考虑埃氏筛。记住“正确的简单算法”远胜于“复杂但可能写错的优化算法”。5. 常见问题与排查技巧实录在实际编码和调试中你会遇到一些典型问题。这里我总结了一份“避坑指南”。5.1 数组越界与溢出这是最常遇到的运行时错误。问题在埃氏筛内层循环for j in range(i*i, n, i)中当i很大时i*i可能超过整数类型的最大值导致溢出变成负数进而使循环变量j初始值为负或者导致条件判断失常。现象程序崩溃段错误或陷入死循环。解决使用更大的数据类型在 C 中将内层循环的索引变量j声明为long long。添加安全判断在循环开始前判断if (i n / i)。因为只有当i*i n时内层循环才有意义。Python 的整数自动支持大数但逻辑判断依然需要。// C 安全写法 for (int i 2; i * i n; i) { // 外层循环条件本身就隐含了 i*i n if (is_prime[i]) { // 保险起见内层循环用 long long for (long long j (long long)i * i; j n; j i) { is_prime[j] false; } } }5.2 结果错误漏筛或多筛症状程序能运行但输出的素数列表明显不对比如少了 2或者包含了合数。排查步骤检查初始状态确认is_prime[0]和is_prime[1]是否已设为False。这是新手最容易忘记的一步。小规模测试用n30这样的小数字手动模拟或打印中间过程。打印出每次标记的合数看是否符合预期。重点检查欧拉筛的终止条件确认if (i % primes[j] 0) break;这行代码是否正确放置在内层循环中标记合数之后。如果放错了位置逻辑就全乱了。检查循环边界埃氏筛的外层循环是for i in range(2, int(n**0.5)1)确保1存在因为range是右开区间。欧拉筛的外层循环是for i in range(2, n)。5.3 性能未达预期可能原因 1使用了低效的数据结构。在 Python 中对于超大n使用list存储布尔值可能比bytearray或array(b)慢。在 C 中vectorint存储is_prime比vectorbool或bitset慢且占用更多内存。优化尝试# Python 使用 bytearray 的埃氏筛 def sieve_eratosthenes_fast(n): is_prime bytearray(b\x01) * n is_prime[0] is_prime[1] 0 for i in range(2, int(n**0.5)1): if is_prime[i]: is_prime[i*i:n:i] b\x00 * ((n - i*i - 1)//i 1) # 切片赋值更快 return [i for i in range(2, n) if is_prime[i]]可能原因 2编译器优化级别低C。确保使用-O2或-O3优化标志进行编译。可能原因 3测量误差。在性能测试时确保计时函数精度足够如 Python 的time.perf_counter并多次运行取平均值避免单次运行的偶然性。5.4 内存消耗过大问题当n为 10^8 时一个布尔数组需要约 100MB 内存假设每个布尔值占1字节。这可能接近或超出某些环境的内存限制。解决方案使用位级压缩C 的std::bitset或std::vectorbool特化版每个元素只占 1 bit。Python 可以使用bitarray第三方库。这样内存消耗可以降到原来的 1/8。分段筛法这是处理超大范围如 10^12素数的进阶技巧。核心思想是内存中只维护一小段区间如 10^6的筛子利用埃氏筛的原理分段处理。这需要更复杂的索引计算但能突破内存限制。只筛奇数除了 2 以外所有素数都是奇数。我们可以只创建一个大小为n/2的数组用来表示奇数3, 5, 7, ...是否为素数。这样可以节省近一半内存但索引映射会稍复杂数字 - 下标的转换。6. 进阶应用与扩展思考掌握了基础筛法我们可以看看它们能解决哪些更复杂的问题。6.1 快速质因数分解利用欧拉筛过程中得到的信息我们可以在线性时间内预处理出每个数的最小质因子LPF。这为后续的质因数分解提供了 O(log n) 的强力工具。def linear_sieve_with_lpf(n): 欧拉筛同时记录每个数的最小质因子 (Least Prime Factor) lpf [0] * (n 1) # lpf[i] 表示 i 的最小质因子 primes [] for i in range(2, n 1): if lpf[i] 0: # i 是素数 lpf[i] i primes.append(i) for p in primes: if p lpf[i] or i * p n: break lpf[i * p] p return primes, lpf def factorize(x, lpf): 利用 lpf 数组快速分解质因数 factors [] while x 1: p lpf[x] cnt 0 while x % p 0: x // p cnt 1 factors.append((p, cnt)) return factors # 预处理 primes, lpf linear_sieve_with_lpf(10**6) # 快速查询 print(factorize(123456, lpf)) # 输出[(2, 6), (3, 1), (643, 1)] 即 2^6 * 3 * 643这个技巧在解决需要大量质因数分解的数学类竞赛题中非常有用。6.2 筛法求欧拉函数/莫比乌斯函数欧拉函数 φ(n) 表示小于等于 n 的正整数中与 n 互质的数的数目。利用欧拉筛的线性特性我们可以在筛素数的同时递推求出每个数的欧拉函数值。def linear_sieve_phi(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-1 for p in primes: if i * p n: break is_prime[i * p] False if i % p 0: # i 和 p 不互质 i*p 与 i 的质因子相同 phi[i * p] phi[i] * p break else: # i 和 p 互质 phi[i * p] phi[i] * (p - 1) return phi phi linear_sieve_phi(20) print(phi[1:]) # 输出 1 到 20 的欧拉函数值类似地也可以求莫比乌斯函数 μ(n)。这体现了筛法作为一种强大的数论预处理工具的通用性。6.3 区间筛法问题求区间 [a, b) 内所有素数其中 a 和 b 可能很大比如 a10^12, b10^1210^6但区间长度 L b-a 相对较小。 直接筛到 b 是不可能的。这时可以用埃氏筛的思想只用一个大小为 L 的数组来筛这个区间。思路先用普通筛法求出所有小于等于 √b 的素数。对于每个求出的素数 p在区间 [a, b) 内找到第一个能被 p 整除的数可能是 p 本身如果 p 在区间内然后标记它的所有倍数。区间内未被标记的数就是素数。def segment_sieve(a, b): 返回区间 [a, b) 内的所有素数 if b 2: return [] # 第一步筛出 [2, sqrt(b)) 内的素数 limit int(b ** 0.5) 1 is_prime_small [True] * limit is_prime_small[0] is_prime_small[1] False for i in range(2, int(limit**0.5)1): if is_prime_small[i]: for j in range(i*i, limit, i): is_prime_small[j] False small_primes [i for i in range(2, limit) if is_prime_small[i]] # 第二步用 small_primes 去筛大区间 [a, b) is_prime_big [True] * (b - a) if a 0: is_prime_big[0] False if a 1: is_prime_big[0] False # 如果区间包含1需要特殊处理 for p in small_primes: # 找到大于等于 a 的第一个 p 的倍数 start max(p * p, ((a p - 1) // p) * p) # 标记区间内的倍数 for j in range(start, b, p): is_prime_big[j - a] False # 收集结果 primes [i a for i, flag in enumerate(is_prime_big) if flag] return primes区间筛法是处理“大海捞针”式素数问题的必备技能。最后关于选择埃氏筛还是欧拉筛我的个人体会是不要过早优化。除非性能分析明确告诉你这里成了瓶颈否则优先使用更简单、更不易出错的埃氏筛。在算法竞赛中10^6 以内的数据两者时间差可能只有几毫秒而调试一段复杂的欧拉筛代码花费的时间远不止这些。当你真正需要处理千万级甚至亿级的数据并且对时间极其敏感时欧拉筛的线性优势才会成为决定性的因素。把基础打牢理解每一种算法背后的“为什么”比死记硬背代码要重要得多。
