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更小的质数标记过了。例如当i5时5*210已经在i2时被标记5*315已经在i3时被标记。从i*i开始可以避免大量重复标记是埃氏筛一个重要的优化点。让我们手动模拟一下找出30以内质数的过程初始化数组所有数标记为质数。i2是质数。标记2*24, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30为合数。i3是质数。标记3*39, 12, 15, 18, 21, 24, 27, 30为合数。注意12、18、24、30已被标记过这是重复标记的来源之一。i4不是质数已在步骤2被标记跳过。i5是质数。标记5*525, 30为合数。i6不是质数跳过。i7是质数。标记7*749大于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; vectorint sieveOfEratosthenes(int n) { // 创建一个布尔向量大小为 n1初始值全部为 true // 索引 i 代表数字 iisPrime[i] 为 true 表示 i 是质数 vectorbool 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; } } } // 收集所有质数 vectorint primes; for (int i 2; i n; i) { if (isPrime[i]) { primes.push_back(i); } } return primes; } int main() { int n 100; vectorint primes sieveOfEratosthenes(n); cout 质数小于等于 n : ; for (int prime : primes) { cout prime ; } cout endl; cout 总数: primes.size() endl; return 0; }代码关键点解析vectorbool isPrime(n1, true): 使用vectorbool是因为它可能被编译器进行位级优化节省空间。n1是为了让索引直接对应数字例如isPrime[5]对应数字5。外层循环条件i * i n: 这是基于数论的一个关键优化。如果一个数n是合数那么它必然有一个不大于sqrt(n)的质因子。因此我们只需要用sqrt(n)以内的质数去筛就够了。用i*i n代替i sqrt(n)可以避免昂贵的sqrt函数调用。内层循环起始点j i * i: 如前所述避免重复标记。内层循环步长j i: 每次增加i正好得到i的下一个倍数写法简洁高效。注意这里存在一个潜在的整数溢出风险。当n接近INT_MAX时i * i可能会溢出。在竞赛或处理极大边界时可以将外层循环条件改为i n / i这是一种更安全的写法。2.3 埃氏筛的效率分析与局限性埃氏筛的时间复杂度是O(n log log n)。这个复杂度已经比O(n sqrt(n))的朴素试除法好太多了。对于n1e6一百万埃氏筛可以瞬间完成而朴素方法则慢得多。然而埃氏筛有一个明显的缺点重复标记。观察上面的模拟过程数字12被质数2和3各标记了一次数字30被质数2、3、5各标记了一次。当n很大时例如1e7或更大这些重复操作会带来不小的开销。虽然时间复杂度依然优秀但在常数因子和实际运行时间上还有优化空间。这就引出了我们下一个要介绍的、更高效的算法——欧拉筛。3. 欧拉筛追求极致的线性时间复杂度欧拉筛也叫线性筛它的目标是让每个合数只被标记一次从而将时间复杂度降到真正的O(n)。这是以稍微增加一点逻辑复杂度为代价的。3.1 算法核心用最小质因子筛除欧拉筛的精髓在于确保每个合数只被它的最小质因子筛掉。我们维护两个数组isPrime[]: 布尔数组标记质数。primes[]: 整型数组动态存储当前找到的所有质数。算法流程如下从2开始遍历到n。如果当前数字i是质数isPrime[i] true就把它加入primes数组。无论i是不是质数都遍历当前已找到的质数列表primes。对于每个质数primes[j]计算composite i * primes[j]。这个数composite一定是一个合数并且primes[j]是它的一个质因子。标记isPrime[composite] false。关键步骤如果i能被primes[j]整除即i % primes[j] 0则在标记完composite后立即跳出内层循环。为什么这里是关键这个break保证了“每个合数只被最小质因子筛掉”。当i % primes[j] 0时说明primes[j]是i的最小质因子因为我们从小到大遍历质数列表。那么对于下一个质数primes[j1]要标记的合数是i * primes[j1]。这个数的最小质因子应该是primes[j]而不是primes[j1]。因为i里已经包含primes[j]这个因子了所以i * primes[j1]可以被写成(i / primes[j]) * primes[j] * primes[j1]它应该在未来某个时刻当外层循环i (i / primes[j]) * primes[j1]时用更小的质因子primes[j]来筛掉。如果现在用primes[j1]筛就重复了。因此此时必须break避免后续的重复标记。3.2 C代码实现与深度剖析#include iostream #include vector using namespace std; vectorint eulerSieve(int n) { vectorbool isPrime(n 1, true); vectorint 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; vectorint 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; }代码关键点与易错点解析long long composite: 这是非常容易忽略但至关重要的一点。当i和primes[j]都很大时它们的乘积可能超出int的范围导致溢出进而引发数组越界访问或无限循环。使用long long是安全的做法。内层循环条件composite n: 当要标记的合数已经大于n时后续的质数相乘会更大所以直接break这是另一个重要的优化。if (i % primes[j] 0) break;: 这是欧拉筛的灵魂。务必理解其原理否则代码就退化为一个低效的、可能重复标记的算法。返回值: 函数直接返回primes向量因为它已经在筛选过程中动态记录了所有质数无需像埃氏筛那样最后再遍历一遍isPrime数组来收集。这既节省了时间也节省了最后收集的循环代码。3.3 欧拉筛 vs 埃氏筛实战场景如何选择特性埃拉托斯特尼筛法 (埃氏筛)欧拉筛 (线性筛)时间复杂度O(n log log n)O(n)空间复杂度O(n)O(n)核心思想用质数标记其所有倍数用最小质因子唯一标记每个合数优点代码极其简单直观易于理解和记忆。对于n 1e7的情况速度已经非常快。理论复杂度最优无重复标记在处理极大范围如n 1e7时优势明显。缺点存在重复标记常数因子较大。对缓存不友好跳跃式访问内存。代码逻辑稍复杂有一个关键break条件需要理解。适用场景算法竞赛中绝大多数情况因为通常n 1e6快速解题的首选。教学入门。对性能有极致要求n非常大如1e7或以上的场景。需要一次性生成质数表的预处理。个人建议对于C入门和绝大多数OJ题目优先掌握埃氏筛。它的代码简单不易写错在数据范围内足够快。花5分钟写对埃氏筛比花15分钟调试欧拉筛的边界条件要划算得多。当你需要解决一个n可能达到1e7甚至更大的问题或者你就是在追求极致的性能时再使用欧拉筛。在掌握埃氏筛的基础上理解欧拉筛的break条件是算法能力的一个很好提升。4. 质数筛的常见变种与实战应用质数筛不仅仅用于生成一个质数列表。基于筛法的思想我们可以进行一些预处理得到非常有用的信息从而高效解决更复杂的问题。4.1 预处理每个数的最小质因子这是欧拉筛一个非常强大的衍生应用。在筛法的过程中我们天然地知道了每个合数是被哪个质数筛掉的这个质数就是它的最小质因子。我们只需要稍微修改一下欧拉筛的代码。#include vector using namespace std; // 返回一个大小为 n1 的数组 spf (Smallest Prime Factor) // spf[i] 表示数字 i 的最小质因子如果 i 是质数则 spf[i] i vectorint getSmallestPrimeFactors(int n) { vectorint spf(n 1, 0); // 初始化为0 vectorint 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))。vectorpairint, int factorize(int x, const vectorint spf) { vectorpairint, 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很大比如a10^9, b10^910^6但区间长度b-a相对较小。我们无法直接开一个大小为b的数组但可以开一个大小为b-a1的数组。思路先用普通的埃氏筛找出sqrt(b)以内的所有质数。创建一个大小为b-a1的布尔数组isPrimeSegment初始化为true表示区间内每个数初始都是质数。对于第1步找到的每一个质数p在区间[a, b]内找到第一个能被p整除的数可能是p本身如果p在区间内的话然后从这个数开始以p为步长将isPrimeSegment中对应的位置标记为false合数。遍历isPrimeSegment值为true的索引需要偏移回实际数字就是区间内的质数。vectorlong long segmentedSieve(long long a, long long b) { if (a 2) a 2; // 1不是质数 int size b - a 1; vectorbool isPrimeSeg(size, true); vectorlong long primesInRange; // 步骤1筛出 sqrt(b) 以内的质数 int limit sqrt(b); vectorbool isPrimeBase(limit 1, true); vectorint 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; vectorbool 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; vectorbool isPrime(n, true); vectorint 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。在实际提交中对于n5e6这样的数据欧拉筛通常比埃氏筛快一些。但埃氏筛的代码更短在时间限制不特别苛刻时是更稳妥的选择。5. 从理解到精通避坑指南与性能优化理解了算法原理和基础代码后在实际编码和解题中还有一些细节和技巧需要注意。5.1 内存使用与vectorbool的陷阱我们一直使用vectorbool因为它节省空间每个元素可能只占1 bit。但这带来了一个潜在问题vectorbool并不是一个标准的容器它进行了特化。这可能导致一些问题取地址操作isPrime[i]可能不合法。在多线程环境下访问可能需要额外注意。如果担心这些问题或者需要与其他期望bool数组的API交互可以使用vectorchar或vectorint用1和0表示真假。这会使内存使用增加通常8倍但对于n在百万级别这通常是可以接受的。// 使用 vectorchar 替代 vectorbool vectorchar isPrime(n 1, 1); // 1 代表 true isPrime[0] isPrime[1] 0; // 0 代表 false5.2 循环边界与溢出防御这是编写筛法尤其是埃氏筛时最容易出错的地方。埃氏筛外层循环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的范围时使用。埃氏筛内层循环for (int j i * i; j n; j i)溢出风险当i很大时例如i46340i*i刚好小于2^31-1i*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;。欧拉筛的乘法溢出前面已经强调(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这三个值观察标记过程是否符合“最小质因子”规则。例如对于欧拉筛当n20时正确的标记顺序应该是i2: 标记4(由质数2标记)i3: 标记6,9(由质数2,3标记)i4: 标记8(由质数2标记)因为4%20标记完8后break。i5: 标记10,15,25(大于20跳出) (由质数2,3,5标记)i6: 标记12(由质数2标记)因为6%20标记完12后break。...通过对比你的程序输出和这个逻辑可以快速定位break条件或循环边界错误。质数筛是算法学习中的一个经典范例它展示了如何通过巧妙的思维转换从判断到标记和数学洞察最小质因子来大幅提升程序效率。掌握它不仅能解决“找质数”这类具体问题更能提升你设计高效算法的能力。先从埃氏筛写起确保无误并能分析其复杂度再挑战欧拉筛理解其精妙的break条件最后尝试它的变种应用。这个过程本身就是一次扎实的算法训练。