1. 项目概述：为什么埃氏筛法依然是算法入门的必修课？
最近在整理一些基础的算法代码库，发现很多朋友在面试或者做小项目时，碰到需要生成素数列表的问题，第一反应还是用最朴素的试除法。这让我想起了当年自己初学算法时，被埃拉托斯特尼筛法（Eratosthenes Sieve）那种简洁高效所震撼的感觉。今天，我们就来彻底拆解这个古老的算法，并用C/C++实现一个工业级可用的版本。无论你是正在啃《算法导论》的学生，还是需要优化某个性能瓶颈的开发者，掌握埃氏筛法都远不止是解决“求素数”这么简单，它背后蕴含的空间换时间、批量标记的思想，在解决大量类似“标记-清除”问题时非常有用。比如，在游戏开发中快速筛选有效实体ID，或者在数据处理中过滤无效数据点，其核心逻辑都是相通的。这篇文章，我会从一个老码农的角度，带你从原理到源码，再到各种优化技巧和坑点，完整地走一遍。
2. 算法核心思想与数学原理拆解
2.1 埃拉托斯特尼的古老智慧：如何“筛”出素数？
埃氏筛法的思想非常直观，就像它的名字一样，是一个“筛选”的过程。我们目标是找出所有小于等于给定整数N的素数。算法从一个布尔数组开始，假设所有数最初都是素数（标记为true）。然后，我们从最小的素数2开始，将其所有的倍数（4, 6, 8, …）标记为非素数（false）。接着，找到下一个未被标记为false的数（此时是3），它一定是素数（因为所有小于它的数的倍数都已经筛过了），然后我们再把3的所有倍数标记掉。如此重复，直到我们处理的数大于√N为止。为什么是√N？这是一个关键优化点：对于任何合数N，它必然有一个因子小于等于√N。因此，当所有小于等于√N的素数的倍数都被筛除后，数组中剩余标记为true的数，就全都是素数了。
这个过程的美妙之处在于，它避免了对于每个数都进行重复的模运算判断。试除法判断一个数n是否为素数，需要尝试从2到√n的所有整数去整除它，时间复杂度是O(√n)。而埃氏筛法通过批量标记倍数，将整体时间复杂度降到了O(N log log N)，这在N很大时（比如上百万、上千万）效率优势是指数级的。
2.2 时间复杂度O(N log log N)的推导与理解
很多资料直接给出了埃氏筛法的时间复杂度是O(N log log N)，但知其然也要知其所以然。这个复杂度是怎么来的呢？我们可以从算法的执行过程来近似估算。
算法的核心操作是标记合数。对于每个素数p，我们需要标记N/p个它的倍数。所以，总标记次数大约是：N/2 + N/3 + N/5 + N/7 + …（对所有≤N的素数p求和 N/p）。
这个和可以近似为N * (1/2 + 1/3 + 1/5 + 1/7 + …)。括号里的部分是所有素数的倒数之和。由数论知识可知，所有素数的倒数之和是发散的，但发散速度极慢，其渐进形式约为log log N + M（其中M是梅塞尔-默滕斯常数）。因此，总操作量约为N * log log N。这也是为什么说埃氏筛法非常高效，log log N是一个增长极其缓慢的函数，当N=10^9时，log log N大约只有5。所以，算法近乎是线性的复杂度。
注意：这里的推导是近似的，严格证明需要更复杂的数论工具，但上述直观理解对于掌握算法性能已经足够。在实际编码中，我们还能通过一些优化技巧，让常数因子变得更小。
3. 基础版本C++实现与逐行解析
我们先从一个最直接、最易于理解的版本开始。这个版本完全遵循算法的原始描述，适合学习和理解。
3.1 代码实现：朴素埃氏筛
#include <iostream> #include <vector> #include <cmath> std::vector<int> sieve_of_eratosthenes_basic(int n) { // 边界条件处理 if (n < 2) { return std::vector<int>(); } // 步骤1：初始化标记数组，默认所有数都是素数 std::vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; // 0和1不是素数 // 步骤2：遍历筛选，上限为sqrt(n) int limit = static_cast<int>(std::sqrt(n)); for (int p = 2; p <= limit; ++p) { // 如果p是素数（未被标记掉） if (is_prime[p]) { // 步骤3：标记p的所有倍数为非素数 // 从p*p开始标记，因为2*p, 3*p, ..., (p-1)*p已经被更小的素数标记过了 for (int multiple = p * p; multiple <= n; multiple += p) { is_prime[multiple] = false; } } } // 步骤4：收集所有素数 std::vector<int> primes; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { primes.push_back(i); } } return primes; }3.2 关键点解析与常见误区
- 数组大小与下标：我们创建了大小为
n+1的vector<bool>，这样下标可以直接对应数字本身，is_prime[i]就表示数字i是否为素数。这是最直观的做法。 - 从
p*p开始标记：这是第一个重要优化。考虑素数p=5，它的倍数5*2=10和5*3=15已经在p=2和p=3时被标记过了。实际上，任何p * k（其中k < p）的合数，其最小质因子一定是小于p的某个数，因此肯定已经被标记过。所以从p*p开始标记，避免了重复工作。 - 循环上限
sqrt(n)：原理如前所述，这是算法的数学基础，能确保所有合数都被筛除。 vector<bool>的特殊性：在C++标准库中，vector<bool>是一个特化版本，它通常将每个布尔值压缩到一个比特（bit）来存储，以节省空间。这带来了空间优势（内存占用约为vector<char>的1/8），但也可能导致访问速度稍慢，且某些操作（如取地址&is_prime[i]）的行为与常规vector不同。在纯筛选场景下，它的利大于弊。
一个新手常掉的坑：在标记倍数的内层循环中，multiple可能会溢出。当p较大时，p * p可能超过int类型的最大值，导致溢出成为负数，从而使循环条件判断出错。对于n在int范围内的常规使用，sqrt(INT_MAX)约为46340，只要n小于这个数的平方（约21亿），p*p就不会在到达n前溢出。但为了代码健壮性，在要求极高的场景，可以使用long long类型作为中间变量。
4. 性能优化进阶：从基础版到工业级
基础版理解了，但它的性能还有很大提升空间。尤其是在处理大规模数据（例如N>10^7）时，缓存命中率、循环步长等因素会显著影响运行时间。下面介绍几种层层递进的优化策略。
4.1 优化一：仅处理奇数——空间和时间减半
这是一个非常有效的优化。我们知道，除了2以外，所有偶数都不是素数。因此，我们可以：
- 单独处理素数2。
- 只对奇数进行筛选。这样，我们的标记数组
is_prime的大小可以减半，只表示奇数。下标i对应的数字是2*i + 1或2*i + 3（取决于映射方式）。 - 在标记倍数时，步长也可以相应调整。因为奇数的倍数间隔是
2*p（例如，用奇数p筛倍数，p, 3p, 5p...都是奇数，但我们需要标记的是奇数中的合数，实际上步长是2*p才能落在奇数索引上）。
这种优化不仅将内存占用减半，也使得内层循环的迭代次数减少，显著提升性能。代码会变得稍复杂，但收益很高。
4.2 优化二：分段筛法（Segmented Sieve）——突破内存限制
标准埃氏筛需要O(N)的内存空间（优化一后是O(N/2)）。当N极大（例如10^9或更大）时，这可能超出可用内存。分段筛法将区间[0, N]分成若干较小的段（例如每段大小等于CPU缓存大小），逐段进行筛选。
核心思想：
- 先用普通筛法求出所有小于等于
√N的“小素数”。 - 对于每一段
[low, high]，创建一个布尔数组标记该段内的数。 - 对于每一个“小素数”
p，找到段内第一个是p的倍数的数（可能需要一点计算），然后在该段内标记p的所有倍数。 - 该段筛选完毕后，收集段内的素数，然后处理下一段。
分段筛法的内存消耗只与段的大小有关，而与N无关，因此可以处理几乎任意大的N，但代价是增加了计算“段内起始位置”的开销和更多的I/O（缓存）操作。
4.3 优化三：使用位运算压缩存储
vector<bool>已经做了比特级压缩。但我们还可以更进一步，手动使用vector<uint64_t>或vector<unsigned char>，并通过位运算来操作特定位。这给了我们更大的控制权，例如可以针对特定的CPU指令集（如POPCNT统计位数）进行优化。不过，这种优化会严重牺牲代码的可读性，通常只在性能瓶颈非常明确的极限优化场景下使用。
4.4 优化版本C++代码示例（奇数优化）
这里给出一个应用了“仅处理奇数”优化的版本，它在可读性和性能之间取得了很好的平衡。
#include <iostream> #include <vector> #include <cmath> std::vector<int> sieve_of_eratosthenes_optimized(int n) { if (n < 2) return std::vector<int>(); if (n == 2) return std::vector<int>{2}; // 初始化：只考虑奇数。is_prime[i] 对应数字 odd = 2*i + 3 // 例如：is_prime[0] -> 3, is_prime[1] -> 5, ... int size = (n - 1) / 2; // 小于等于n的奇数的个数 std::vector<bool> is_prime(size, true); // 手动将素数2加入结果集 std::vector<int> primes = {2}; // 外循环遍历所有可能的奇数因子 // 数字 odd = 2*i + 3，其平方为 (2*i+3)^2。对应的索引需要转换。 // 筛选上限是 sqrt(n) 对应的奇数索引 int limit = (static_cast<int>(std::sqrt(n)) - 1) / 2; for (int i = 0; i <= limit; ++i) { if (is_prime[i]) { int odd = 2 * i + 3; // 当前素数 p primes.push_back(odd); // 标记当前素数p的倍数（只标记奇数倍） // 起始位置：p * p 是奇数，其索引 j = (p*p - 3) / 2 // 步长：p的奇数倍间隔是 2*p，在索引数组上步长为 p (因为索引差值是 p) // 详细推导：下一个要标记的数是 p*(p+2) = p*p + 2p，索引增加量为 p long long start = static_cast<long long>(odd) * odd; for (long long j = (start - 3) / 2; j < size; j += odd) { is_prime[j] = false; } } } // 收集剩余的素数 for (int i = limit + 1; i < size; ++i) { if (is_prime[i]) { primes.push_back(2 * i + 3); } } return primes; }代码解读与心得：
size = (n-1)/2计算了从3到n之间奇数的个数。- 索引
i与真实奇数odd的映射关系是核心：odd = 2*i + 3。这样i=0对应3。 - 内层循环的起始
j = (p*p - 3) / 2和步长odd，是通过数学关系推导出来的。这是该优化版本最难理解的部分，务必亲手演算一下。 - 使用
long long类型计算start，防止odd*odd在n很大时溢出。 - 这个版本比基础版快大约一倍，内存占用减半。
5. 内存与性能的权衡：vector<bool>的陷阱与替代方案
前面提到了vector<bool>可能存在的性能陷阱。虽然它节省内存，但比特操作可能比直接字节操作慢。我们可以做一个简单的对比测试：
方案A：使用vector<bool>
- 优点：内存占用最小。
- 缺点：单个位的读写可能不是原子操作，速度可能稍慢，且不能取地址。
方案B：使用vector<char>或vector<uint8_t>
- 优点：访问速度是标准的字节操作，通常更快，行为符合直觉。
- 缺点：内存占用是
vector<bool>的8倍。
如何选择？
- 如果
N非常大（例如 > 10^8），内存是首要瓶颈，优先使用vector<bool>。 - 如果
N在中等规模（例如 10^6 ~ 10^7），且追求极限速度，可以尝试vector<char>。CPU缓存命中率可能因此下降，需要实际测试。 - 在“仅处理奇数”的优化中，由于数据量减半，使用
vector<char>的内存压力也减小了，此时用它来换取可能的加速是更可行的。
一个简单的性能测试框架可以帮助你决策：
#include <chrono> // ... 分别实现 vector<bool> 和 vector<char> 版本的筛法 ... auto start = std::chrono::high_resolution_clock::now(); auto primes = sieve_with_vector_bool(n); auto end = std::chrono::high_resolution_clock::now(); std::cout << “vector<bool> time: “ << std::chrono::duration<double>(end-start).count() << “s\n”; // 同理测试 vector<char> 版本在我的多次实测中，对于N在1e7量级，优化后的奇数筛法，vector<char>版本有时能比vector<bool>版本快10%-20%，但内存占用确实多了8倍。这是一个典型的时空权衡。
6. 实战应用与问题排查指南
埃氏筛法不仅用于生成素数表，其思想可以迁移到许多场景。
6.1 应用场景延伸
- 质因数分解预处理：生成一个
min_prime数组，min_prime[i]存储数字i的最小质因数。这可以通过在埃氏筛法标记合数时，同时记录是哪个素数将其标记的来实现。有了这个数组，对任意数进行质因数分解可以在 O(log n) 时间内完成。 - 欧拉函数（Euler‘s Totient）预处理：类似地，可以在筛法过程中计算每个数的欧拉函数 φ(n)，用于数论和密码学相关计算。
- 区间素数统计：结合分段筛法，可以高效回答诸如“区间 [a, b] 内有多少素数”的问题，这是某些编程竞赛的经典题型。
6.2 常见问题与调试技巧
即使理解了算法，实现时也可能遇到一些隐蔽的问题。下面是一个常见问题速查表：
| 问题现象 | 可能原因 | 排查与解决 |
|---|---|---|
| 程序输出漏掉了一些明显的素数（如3,5）。 | 1. 数组初始化错误，is_prime[0]和is_prime[1]未设为false。2. 在“仅奇数”优化中，索引与数字的映射关系算错。 | 1. 检查初始化代码。 2. 对于优化版，用小数据（如n=30）手动模拟运行，打印出每个步骤的索引 i和对应的数字odd，核对映射。 |
| 程序输出包含合数（如9,15）。 | 内层循环标记倍数时，起始位置或步长错误。最常见的是没有从p*p开始，或者步长不是p而是1。 | 1. 确认内循环起始为int multiple = p * p。2. 确认步长为 multiple += p。3. 在优化版中，确认步长推导正确。 |
| 当n较大时（如1e7），程序运行异常慢或内存不足。 | 1. 使用了未优化的基础版本。 2. 使用了 vector<int>而非vector<bool>来存储标记，内存暴涨。3. 开了过大的静态数组（如 bool is_prime[100000001]）导致栈溢出。 | 1. 采用“仅处理奇数”优化。 2. 确保使用 vector<bool>。3. 对于极大n，考虑分段筛法。大型数组务必在堆上分配（用 vector）。 |
| 程序在n较大时崩溃（如n=1000000000）。 | 整数溢出。在计算p*p或循环变量时，int类型溢出。 | 将内层循环中涉及p*p的计算和循环变量改为long long类型。 |
| 结果正确，但性能不达预期。 | 1. 编译器优化未开启。 2. 缓存不友好。基础版本的内存访问模式是跳跃的（步长为p），对缓存不友好。 | 1. 编译时添加优化标志（如g++的-O2或-O3）。2. 考虑使用分段筛法，使每段数据能更好地装入CPU缓存。 |
一个实用的调试技巧：实现一个简单的暴力试除法函数bool is_prime_naive(int n)，用于验证你的筛法在小范围（例如n<=100000）内的结果是否正确。将筛法得到的素数列表与暴力法逐个对比，可以快速定位错误。
7. 不同场景下的选型与扩展思考
学了一个算法，更要懂得在什么场合用它。埃氏筛法不是万能的。
何时使用埃氏筛法？
- 需要获取一个范围内的所有素数。这是它的主场。
- 需要频繁查询某个数是否为素数。可以预先筛好，之后O(1)查询。
- 需要数字的某些数论函数值（如最小质因数、欧拉函数）。可以在筛法过程中一并求出。
何时选择其他方法？
- 仅判断单个大数是否为素数：使用米勒-拉宾素性测试，时间复杂度更低。
- 需要获取第n个素数：埃氏筛法需要先估计一个范围，筛出所有素数后再找，可能浪费计算。可以使用更高级的算法（如Meissel-Lehmer算法）。
- 范围极大但区间很窄：例如判断
[10^18, 10^18+1000]内的素数，用区间筛法（基于埃氏筛思想）更合适。
扩展思考：线性筛法（欧拉筛）埃氏筛法的一个小缺陷是，有些合数会被它的多个质因子重复标记（例如30，会被2、3、5各标记一次）。虽然不影响复杂度，但存在优化空间。线性筛法（也称欧拉筛）保证了每个合数只被它的最小质因子标记一次，时间复杂度是严格的O(N)。它的实现稍复杂，需要额外维护一个素数列表，并在筛的过程中用已得到的素数去标记。对于追求极致常数优化的场景，线性筛是更好的选择。但埃氏筛法因其极致的简洁性，在大多数情况下依然是首选。
最后，我个人的一点体会是，埃氏筛法就像算法世界里的“hello world”，它简单到足以让初学者理解，又深刻到包含了空间换时间、预处理、批量操作等多个核心思想。把它吃透，意义远不止于求素数。下次当你遇到需要“批量过滤”的问题时，不妨想想，能不能用“筛”的思想来解决？
