1. 从“暴力枚举”到“筛法”：为什么我们需要质数筛？

刚接触C++编程，尤其是开始刷一些算法题时，质数判断和生成几乎是绕不开的坎。很多新手的第一反应是：判断一个数n是不是质数，那还不简单？从2循环到n-1，看看有没有能整除它的数不就行了？这个思路没错，这就是最朴素的“试除法”。但当你遇到题目要求“找出1到1000000之间的所有质数”时，用试除法挨个判断，程序大概率会超时。这时，你就需要“质数筛”这个利器了。

质数筛，顾名思义，就是像筛子一样，把合数（非质数）过滤掉，留下质数。它的核心思想不是去“证明”一个数是质数，而是去“标记”出所有不是质数的数。这种“反其道而行之”的思路，在处理大量数据时，效率会有质的飞跃。对于C++入门者来说，理解并掌握至少一种质数筛算法，不仅是解决特定题目的需要，更是培养“算法思维”的重要一步——从关注单个元素的属性，转向思考如何高效处理整个集合。今天，我们就来彻底搞懂质数筛，从最经典的埃拉托斯特尼筛法（埃氏筛）到更高效的欧拉筛（线性筛），我会结合代码和大量注释，让你不仅会写，更明白为什么这么写。

2. 埃拉托斯特尼筛法：直观易懂的筛法入门

埃氏筛是历史上最古老的筛法，以其发明者古希腊数学家埃拉托斯特尼命名。它的逻辑非常直观，非常适合作为理解筛法思想的起点。

2.1 算法原理与模拟过程

我们用一个布尔数组isPrime来标记每个数是否是质数。初始时，假设所有数都是质数（isPrime[i] = true）。 算法的核心步骤是：从最小的质数2开始，如果当前数字i是质数（即isPrime[i] == true），那么就把i的所有倍数（从i*i开始）都标记为合数（isPrime[j] = false）。

为什么从i*i开始标记？因为对于任意一个小于i*i的合数k*i(k < i)，它一定已经被一个比i更小的质数标记过了。例如，当i=5时，5*2=10已经在i=2时被标记，5*3=15已经在i=3时被标记。从i*i开始可以避免大量重复标记，是埃氏筛一个重要的优化点。

让我们手动模拟一下找出30以内质数的过程：

1. 初始化数组，所有数标记为质数。
2. i=2，是质数。标记2*2=4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30为合数。
3. i=3，是质数。标记3*3=9, 12, 15, 18, 21, 24, 27, 30为合数。（注意12、18、24、30已被标记过，这是重复标记的来源之一）。
4. i=4，不是质数（已在步骤2被标记），跳过。
5. i=5，是质数。标记5*5=25, 30为合数。
6. i=6，不是质数，跳过。
7. i=7，是质数。标记7*7=49，大于30，循环结束。 最终，数组中仍为true的索引（从2开始）就是质数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29。

2.2 C++代码实现与逐行解析

下面是用C++实现埃氏筛的经典代码，用于筛选n以内的所有质数。

#include <iostream> #include <vector> using namespace std; vector<int> sieveOfEratosthenes(int n) { // 创建一个布尔向量，大小为 n+1，初始值全部为 true // 索引 i 代表数字 i，isPrime[i] 为 true 表示 i 是质数 vector<bool> isPrime(n + 1, true); // 0 和 1 不是质数 isPrime[0] = isPrime[1] = false; // 核心筛法过程 for (int i = 2; i * i <= n; ++i) { // 优化1：外层循环只需到 sqrt(n) if (isPrime[i]) { // 如果 i 是质数 // 从 i*i 开始，标记 i 的所有倍数为合数 // 优化2：使用 j += i 来递增，直接找到倍数 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } // 收集所有质数 vector<int> primes; for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); } } return primes; } int main() { int n = 100; vector<int> primes = sieveOfEratosthenes(n); cout << "质数（小于等于 " << n << "）: "; for (int prime : primes) { cout << prime << " "; } cout << endl; cout << "总数: " << primes.size() << endl; return 0; }

代码关键点解析：

1. vector<bool> isPrime(n+1, true): 使用vector<bool>是因为它可能被编译器进行位级优化，节省空间。n+1是为了让索引直接对应数字（例如isPrime[5]对应数字5）。
2. 外层循环条件i * i <= n: 这是基于数论的一个关键优化。如果一个数n是合数，那么它必然有一个不大于sqrt(n)的质因子。因此，我们只需要用sqrt(n)以内的质数去筛就够了。用i*i <= n代替i <= sqrt(n)可以避免昂贵的sqrt函数调用。
3. 内层循环起始点j = i * i: 如前所述，避免重复标记。
4. 内层循环步长j += i: 每次增加i，正好得到i的下一个倍数，写法简洁高效。

注意：这里存在一个潜在的整数溢出风险。当n接近INT_MAX时，i * i可能会溢出。在竞赛或处理极大边界时，可以将外层循环条件改为i <= n / i，这是一种更安全的写法。

2.3 埃氏筛的效率分析与局限性

埃氏筛的时间复杂度是O(n log log n)。这个复杂度已经比O(n sqrt(n))的朴素试除法好太多了。对于n=1e6（一百万），埃氏筛可以瞬间完成，而朴素方法则慢得多。

然而，埃氏筛有一个明显的缺点：重复标记。观察上面的模拟过程，数字12被质数2和3各标记了一次，数字30被质数2、3、5各标记了一次。当n很大时（例如1e7或更大），这些重复操作会带来不小的开销。虽然时间复杂度依然优秀，但在常数因子和实际运行时间上，还有优化空间。这就引出了我们下一个要介绍的、更高效的算法——欧拉筛。

3. 欧拉筛：追求极致的线性时间复杂度

欧拉筛，也叫线性筛，它的目标是让每个合数只被标记一次，从而将时间复杂度降到真正的O(n)。这是以稍微增加一点逻辑复杂度为代价的。

3.1 算法核心：用最小质因子筛除

欧拉筛的精髓在于：确保每个合数只被它的最小质因子筛掉。

我们维护两个数组：

1. isPrime[]: 布尔数组，标记质数。
2. primes[]: 整型数组，动态存储当前找到的所有质数。

算法流程如下：

1. 从2开始遍历到n。
2. 如果当前数字i是质数（isPrime[i] == true），就把它加入primes数组。
3. 无论i是不是质数，都遍历当前已找到的质数列表primes。
4. 对于每个质数primes[j]，计算composite = i * primes[j]。这个数composite一定是一个合数，并且primes[j]是它的一个质因子。
5. 标记isPrime[composite] = false。
6. 关键步骤：如果i能被primes[j]整除（即i % primes[j] == 0），则在标记完composite后，立即跳出内层循环。

为什么这里是关键？这个break保证了“每个合数只被最小质因子筛掉”。

• 当i % primes[j] == 0时，说明primes[j]是i的最小质因子（因为我们从小到大遍历质数列表）。
• 那么对于下一个质数primes[j+1]，要标记的合数是i * primes[j+1]。这个数的最小质因子应该是primes[j]，而不是primes[j+1]。因为i里已经包含primes[j]这个因子了，所以i * primes[j+1]可以被写成(i / primes[j]) * primes[j] * primes[j+1]，它应该在未来某个时刻，当外层循环i' = (i / primes[j]) * primes[j+1]时，用更小的质因子primes[j]来筛掉。如果现在用primes[j+1]筛，就重复了。
• 因此，此时必须break，避免后续的重复标记。

3.2 C++代码实现与深度剖析

#include <iostream> #include <vector> using namespace std; vector<int> eulerSieve(int n) { vector<bool> isPrime(n + 1, true); vector<int> primes; // 用于存储找到的质数 isPrime[0] = isPrime[1] = false; for (int i = 2; i <= n; ++i) { // 步骤1：如果i是质数，加入质数列表 if (isPrime[i]) { primes.push_back(i); } // 步骤2：遍历当前质数列表 for (int j = 0; j < primes.size(); ++j) { // 计算要标记的合数 long long composite = (long long)i * primes[j]; // 如果合数超出范围，中断内层循环 if (composite > n) { break; } // 标记合数 isPrime[composite] = false; // **核心**：如果i能被当前质数整除，则跳出循环 if (i % primes[j] == 0) { break; } } } return primes; // primes本身就包含了所有质数，无需再次收集 } int main() { int n = 100; vector<int> primes = eulerSieve(n); cout << "质数（小于等于 " << n << "）: "; for (int prime : primes) { cout << prime << " "; } cout << endl; cout << "总数: " << primes.size() << endl; // 验证isPrime数组也可以使用 // for (int i = 2; i <= n; ++i) { // if (isPrime[i]) cout << i << " "; // } return 0; }

代码关键点与易错点解析：

1. long long composite: 这是非常容易忽略但至关重要的一点。当i和primes[j]都很大时，它们的乘积可能超出int的范围，导致溢出，进而引发数组越界访问或无限循环。使用long long是安全的做法。
2. 内层循环条件composite > n: 当要标记的合数已经大于n时，后续的质数相乘会更大，所以直接break，这是另一个重要的优化。
3. if (i % primes[j] == 0) break;: 这是欧拉筛的灵魂。务必理解其原理，否则代码就退化为一个低效的、可能重复标记的算法。
4. 返回值: 函数直接返回primes向量，因为它已经在筛选过程中动态记录了所有质数，无需像埃氏筛那样最后再遍历一遍isPrime数组来收集。这既节省了时间，也节省了（最后收集的）循环代码。

3.3 欧拉筛 vs 埃氏筛：实战场景如何选择？

个人建议：

• 对于C++入门和绝大多数OJ题目，优先掌握埃氏筛。它的代码简单，不易写错，在数据范围内足够快。花5分钟写对埃氏筛，比花15分钟调试欧拉筛的边界条件要划算得多。
• 当你需要解决一个n可能达到1e7甚至更大的问题，或者你就是在追求极致的性能时，再使用欧拉筛。在掌握埃氏筛的基础上，理解欧拉筛的break条件，是算法能力的一个很好提升。

4. 质数筛的常见变种与实战应用

质数筛不仅仅用于生成一个质数列表。基于筛法的思想，我们可以进行一些预处理，得到非常有用的信息，从而高效解决更复杂的问题。

4.1 预处理每个数的最小质因子

这是欧拉筛一个非常强大的衍生应用。在筛法的过程中，我们天然地知道了每个合数是被哪个质数筛掉的，这个质数就是它的最小质因子。我们只需要稍微修改一下欧拉筛的代码。

#include <vector> using namespace std; // 返回一个大小为 n+1 的数组 spf (Smallest Prime Factor) // spf[i] 表示数字 i 的最小质因子，如果 i 是质数，则 spf[i] == i vector<int> getSmallestPrimeFactors(int n) { vector<int> spf(n + 1, 0); // 初始化为0 vector<int> primes; for (int i = 2; i <= n; ++i) { if (spf[i] == 0) { // i 是质数 spf[i] = i; // 质数的最小质因子是它本身 primes.push_back(i); } for (int j = 0; j < primes.size(); ++j) { long long composite = (long long)i * primes[j]; if (composite > n) break; spf[composite] = primes[j]; // 记录合数的最小质因子 if (i % primes[j] == 0) break; } } return spf; }

应用场景：

• 质因数分解：给定一个数x，利用spf数组可以以O(log x)的时间复杂度对其进行质因数分解，而不是O(sqrt(x))。

  vector<pair<int, int>> factorize(int x, const vector<int>& spf) { vector<pair<int, int>> factors; // (质因子, 指数) while (x > 1) { int p = spf[x]; int cnt = 0; while (x % p == 0) { x /= p; cnt++; } factors.emplace_back(p, cnt); } return factors; }

• 计算欧拉函数：欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的数目。利用质因数分解结果，可以快速计算φ(n)。

4.2 区间筛法：筛出超大范围内的质数

有时问题会问：求区间[a, b]内所有质数，其中a和b很大（比如a=10^9, b=10^9+10^6），但区间长度b-a相对较小。我们无法直接开一个大小为b的数组，但可以开一个大小为b-a+1的数组。

思路：

1. 先用普通的埃氏筛找出sqrt(b)以内的所有质数。
2. 创建一个大小为b-a+1的布尔数组isPrimeSegment，初始化为true，表示区间内每个数初始都是质数。
3. 对于第1步找到的每一个质数p，在区间[a, b]内找到第一个能被p整除的数（可能是p本身，如果p在区间内的话），然后从这个数开始，以p为步长，将isPrimeSegment中对应的位置标记为false（合数）。
4. 遍历isPrimeSegment，值为true的索引（需要偏移回实际数字）就是区间内的质数。

vector<long long> segmentedSieve(long long a, long long b) { if (a < 2) a = 2; // 1不是质数 int size = b - a + 1; vector<bool> isPrimeSeg(size, true); vector<long long> primesInRange; // 步骤1：筛出 sqrt(b) 以内的质数 int limit = sqrt(b); vector<bool> isPrimeBase(limit + 1, true); vector<int> basePrimes; for (int i = 2; i <= limit; ++i) { if (isPrimeBase[i]) { basePrimes.push_back(i); for (int j = i * i; j <= limit; j += i) { isPrimeBase[j] = false; } } } // 步骤2：用基质数筛区间 for (int p : basePrimes) { // 找到区间内第一个能被p整除的数 long long start = max((long long)p * p, ((a + p - 1) / p) * p); for (long long j = start; j <= b; j += p) { isPrimeSeg[j - a] = false; // 偏移索引 } } // 步骤3：收集结果 for (long long i = a; i <= b; ++i) { if (isPrimeSeg[i - a]) { primesInRange.push_back(i); } } return primesInRange; }

注意：这里start的计算((a + p - 1) / p) * p是向上取整的整数除法技巧，用于找到大于等于a的第一个p的倍数。

4.3 实战例题解析：计数质数

LeetCode上有一道经典题目204. 计数质数。题目要求统计所有小于非负整数n的质数的数量。这就是质数筛的“标准应用题”。

埃氏筛解法：

class Solution { public: int countPrimes(int n) { if (n <= 2) return 0; vector<bool> isPrime(n, true); // 索引0到n-1，代表数字0到n-1 isPrime[0] = isPrime[1] = false; int count = 0; // 优化：只筛到 sqrt(n) for (int i = 2; i * i < n; ++i) { if (isPrime[i]) { // 从 i*i 开始筛，注意边界是 n for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } } // 统计 for (int i = 2; i < n; ++i) { if (isPrime[i]) count++; } return count; } };

欧拉筛解法：

class Solution { public: int countPrimes(int n) { if (n <= 2) return 0; vector<bool> isPrime(n, true); vector<int> primes; isPrime[0] = isPrime[1] = false; for (int i = 2; i < n; ++i) { if (isPrime[i]) primes.push_back(i); for (int j = 0; j < primes.size(); ++j) { long long composite = (long long)i * primes[j]; if (composite >= n) break; // 注意这里是 >= n isPrime[composite] = false; if (i % primes[j] == 0) break; } } return primes.size(); // primes列表的长度就是答案 } };

踩坑点：

• 边界条件：题目要求“小于n”，所以我们的循环和数组大小都是< n，而不是<= n。在埃氏筛的外层循环中，条件应是i * i < n。
• 初始化：isPrime[0]和isPrime[1]要设为false。
• 欧拉筛的溢出：计算composite时必须使用long long，并在判断composite >= n时及时break。

在实际提交中，对于n=5e6这样的数据，欧拉筛通常比埃氏筛快一些。但埃氏筛的代码更短，在时间限制不特别苛刻时是更稳妥的选择。

5. 从理解到精通：避坑指南与性能优化

理解了算法原理和基础代码后，在实际编码和解题中，还有一些细节和技巧需要注意。

5.1 内存使用与vector<bool>的陷阱

我们一直使用vector<bool>，因为它节省空间（每个元素可能只占1 bit）。但这带来了一个潜在问题：vector<bool>并不是一个标准的容器，它进行了特化。这可能导致一些问题：

• 取地址操作（&isPrime[i]）可能不合法。
• 在多线程环境下访问可能需要额外注意。

如果担心这些问题，或者需要与其他期望bool数组的API交互，可以使用vector<char>或vector<int>，用1和0表示真假。这会使内存使用增加（通常8倍），但对于n在百万级别，这通常是可以接受的。

// 使用 vector<char> 替代 vector<bool> vector<char> isPrime(n + 1, 1); // 1 代表 true isPrime[0] = isPrime[1] = 0; // 0 代表 false

5.2 循环边界与溢出防御

这是编写筛法，尤其是埃氏筛时最容易出错的地方。

1. 埃氏筛外层循环：for (int i = 2; i * i <= n; ++i)

   • 错误写法：for (int i = 2; i <= sqrt(n); ++i)。每次循环都计算sqrt(n)，效率低。
   • 安全写法：for (int i = 2; i <= n / i; ++i)。完全避免乘法溢出，推荐在不确定n的范围时使用。

2. 埃氏筛内层循环：for (int j = i * i; j <= n; j += i)

   • 溢出风险：当i很大时（例如i=46340，i*i刚好小于2^31-1），i*i可能溢出。对于int范围的n，使用i <= n / i的外层条件已经保证了i*i <= n，所以i*i不会溢出int。但为了绝对安全，或者使用long long的n时，内层起始点应写为：long long j = (long long)i * i;或者long long j = i; j *= i;。

3. 欧拉筛的乘法溢出：前面已经强调，(long long)i * primes[j]是必须的。

5.3 预处理与查询：空间换时间的艺术

质数筛的典型应用模式是“预处理-查询”。在程序初始化时（或根据输入的最大范围），用O(n)或O(n log log n)的时间预处理出整个质数表或最小质因子表。之后，每次查询一个数是否为质数，或者获取其质因数，都只需要O(1)或O(log n)的时间。这在处理大量查询的题目中优势巨大。

例如，在解决需要频繁判断质数或进行质因数分解的问题时，在main函数开头调用一次eulerSieve(MAX_N)或getSmallestPrimeFactors(MAX_N)，将结果存储在全局变量中，后续所有函数都可以直接使用这个预处理好的数组，效率极高。

5.4 调试技巧：小数据模拟与打印中间状态

当你怀疑筛法代码有bug时，最好的调试方法是用一个很小的n（比如20或30），一步步模拟程序运行，或者打印出中间状态。

对于埃氏筛，可以在内层标记循环后打印isPrime数组。 对于欧拉筛，可以在每次标记合数composite时，打印出i, primes[j], composite这三个值，观察标记过程是否符合“最小质因子”规则。

例如，对于欧拉筛，当n=20时，正确的标记顺序应该是：

• i=2: 标记4(由质数2标记)
• i=3: 标记6,9(由质数2,3标记)
• i=4: 标记8(由质数2标记)，因为4%2==0，标记完8后break。
• i=5: 标记10,15,25(大于20，跳出) (由质数2,3,5标记)
• i=6: 标记12(由质数2标记)，因为6%2==0，标记完12后break。
• ...

通过对比你的程序输出和这个逻辑，可以快速定位break条件或循环边界错误。

质数筛是算法学习中的一个经典范例，它展示了如何通过巧妙的思维转换（从判断到标记）和数学洞察（最小质因子）来大幅提升程序效率。掌握它，不仅能解决“找质数”这类具体问题，更能提升你设计高效算法的能力。先从埃氏筛写起，确保无误并能分析其复杂度；再挑战欧拉筛，理解其精妙的break条件；最后尝试它的变种应用。这个过程本身，就是一次扎实的算法训练。