1. 项目概述为什么我们需要质数筛在C算法学习的道路上质数判断与筛选是一个绕不开的经典课题。无论是解决一些在线评测平台OJ上的数学问题还是为更复杂的加密算法、哈希函数打基础高效地找出一定范围内的所有质数都是一项核心技能。很多初学者包括当年的我都是从最朴素的“试除法”开始的——对于一个数n用2到√n之间的所有整数去试除。这种方法理解起来简单但当题目要求找出1到10^6甚至更大范围内的所有质数时其O(n√n)的时间复杂度就完全不够看了程序会慢到令人无法接受。这就是“质数筛”算法登场的时刻。它的核心思想不再是“单个判断”而是“批量筛选”。通过一系列巧妙的标记操作我们可以在接近线性的时间内高效地“筛”出目标范围内的所有质数。今天我们就来深入剖析三种主流的质数筛算法普通筛法、埃拉托斯特尼筛法埃氏筛和欧拉筛法线性筛。我会结合自己多年刷题和教学的经验不仅告诉你它们怎么写更会讲清楚为什么这么写以及在实际编码中会遇到哪些坑如何避开它们。2. 算法核心思路与演进逻辑质数筛算法的演进是一部典型的算法优化史其核心矛盾始终围绕着“时间效率”和“空间效率”以及如何减少“重复标记”这个关键问题。2.1 从直觉出发普通筛法朴素筛法我们先从最符合直觉的“普通筛法”开始。它的思路非常直接假设我们要找出从2到N的所有质数。初始化一个布尔数组isPrime[]大小为N1默认所有元素为true表示我们先假设所有数都是质数。从2开始遍历到N。对于当前遍历到的数字i如果isPrime[i]为true那么我不仅认为i是质数还认为i的所有倍数i*2,i*3,i*4...都一定是合数因为它们都有i这个非1非自身的因子。于是我们将i的所有倍数j对应的isPrime[j]标记为false。遍历完成后数组中仍为true的下标就是质数。为什么称之为“普通”或“朴素”它的时间复杂度是 O(N log log N)。虽然比试除法快很多但它存在大量的重复标记。例如数字12会被标记多次当i2时作为2的倍数被标记一次当i3时作为3的倍数又被标记一次当i6时还会被标记。这种重复劳动就是性能的浪费也是我们优化的突破口。注意很多初学者会混淆“普通筛法”和“试除法”。请记住筛法的操作对象是一个范围通过标记倍数来排除合数而试除法的对象是单个数字通过验证是否有非1非自身的因子来判断。两者目的相同但思路和效率天差地别。2.2 第一次优化埃拉托斯特尼筛法埃氏筛埃氏筛是对普通筛法的一次显著优化。古希腊数学家埃拉托斯特尼提出了一个关键观察一个合数必然可以被某个质因子筛掉。基于此埃氏筛的算法步骤优化如下同样初始化isPrime[]数组全部设为true。从2开始遍历到N。对于当前数字i如果isPrime[i]为true那么 a. 首先将i加入质数列表。 b. 然后仅当i是质数时才去标记它的倍数。这是一个至关重要的区别在普通筛法中即使i是合数比如4我们也会去标记4的倍数这完全是多余的因为4本身已经被它的质因子2筛过了。标记倍数时可以从i * i开始。为什么不是2*i开始因为对于质数i像2*i,3*i...(i-1)*i这些数它们一定有一个比i小的质因子比如23等所以在之前遍历到更小的质数时就已经被标记过了。从i*i开始标记避免了这部分重复操作。埃氏筛的效率提升时间复杂度约为 O(N log log N)。虽然量级上和普通筛法一样但因为去除了合数的标记操作并且标记起点后移实际运行速度要快上好几倍。它是竞赛和工程中非常常用且高效的质数筛算法在N不超过10^7时表现非常出色。2.3 终极优化欧拉筛法线性筛埃氏筛已经很快了但它依然无法避免重复标记尽管比普通筛少得多。例如合数30 2 * 15 3 * 10 5 * 6在埃氏筛中当i2时标记30当i3时标记30当i5时还会标记30。实际上我们希望每个合数只被标记一次。欧拉筛线性筛实现了这个目标达到了理论上的 O(N) 时间复杂度。它的核心思想是让每个合数只被它的最小质因子筛掉。如何保证这一点算法需要维护一个质数列表primes[]。同样初始化isPrime[]数组。从2遍历到N。对于每个数字i a. 如果isPrime[i]为true则将i加入质数列表primes。 b. 无论i是否是质数都遍历当前的质数列表primes。令当前遍历到的质数为primes[j]。 - 计算composite i * primes[j]。这个数composite一定是一个合数且primes[j]是它的一个质因子。 - 将isPrime[composite]标记为false。 -关键步骤如果i % primes[j] 0则跳出对质数列表的遍历。为什么那个break如此关键这正是保证“每个合数只被最小质因子筛掉”的灵魂所在。当i % primes[j] 0时说明primes[j]是i的一个质因子且是当前最小的因为我们从小到大遍历质数列表。设i primes[j] * k。那么对于下一个质数primes[j1]要标记的合数是i * primes[j1] (primes[j] * k) * primes[j1] primes[j] * (k * primes[j1])。你会发现这个合数primes[j] * (k * primes[j1])它有一个更小的质因子primes[j]。它本应该在将来当i遍历到(k * primes[j1])这个更大的数并且用primes[j]去筛的时候被标记。如果现在用primes[j1]把它筛了就导致了重复标记因为primes[j]比primes[j1]小primes[j]才是它的最小质因子。因此当i % primes[j] 0时必须break以保证后续更大的合数留给其最小质因子primes[j]去筛。3. 核心细节解析与实操要点理解了思路我们来看看在把思路转化成C代码时有哪些魔鬼细节。3.1 数据结构的选择数组与向量质数筛的核心数据结构是一个用于标记的数组。在C中我们有两种主要选择C风格原生数组bool isPrime[N1];。性能最好内存连续。但有一个致命问题如果N很大比如1e8这个数组作为局部变量可能会造成栈溢出因为栈空间有限。除非定义为全局变量或静态变量。std::vectorboolvectorbool isPrime(N1, true);。这是更推荐的做法。vector将数据存储在堆上避免了栈溢出风险。而且vectorbool是标准库的一个特化版本它通常每个bool只占1个比特bit而不是1个字节byte可以节省高达87.5%的内存这对于需要处理超大范围如数亿级别的质数筛至关重要。实操心得无脑用vectorbool。在算法竞赛和大多数工程场景中它都是最佳选择。不用担心它的位操作性能编译器会优化得很好。唯一需要注意的是vectorbool的迭代器行为可能不符合标准容器迭代器的所有要求但在质数筛这种下标访问为主的场景中完全不受影响。3.2 范围与边界处理“差一错误”Off-by-one error是这里最常见的坑。数组大小如果我们需要筛出[1, N]的质数数组大小应设为N1以便用下标i直接代表数字i。通常我们忽略下标0从下标1或2开始使用。循环边界遍历数字i的范围通常是for (int i 2; i N; i)。注意是 N。埃氏筛标记倍数的起始点for (long long j (long long)i * i; j N; j i)。这里有两个关键点1) 起始是i*i不是2*i。2) 循环条件j N。埃氏筛的i循环优化外层循环i可以只遍历到sqrt(N)。因为如果i是大于sqrt(N)的合数它一定有一个小于等于sqrt(N)的质因子所以它早就被标记了如果它是大于sqrt(N)的质数它的倍数i*i已经大于N无需标记。因此可以写成for (int i 2; i * i N; i)。但是这之后我们还需要一个单独的循环来收集所有isPrime[i]为true的i从2到N才能得到完整的质数列表。这个优化减少了标记操作但增加了一次收集循环。线性筛的内层循环边界for (int j 0; j primes.size() (long long)i * primes[j] N; j)。边界条件有两个不能超出质数列表范围并且生成的合数不能超过N。3.3 整数溢出的预防这是另一个高频踩坑点。在标记倍数时i * i或i * primes[j]很可能超过int类型的最大值约21亿导致溢出进而使循环判断失常可能引发数组越界访问导致程序崩溃。解决方案在计算乘积时使用范围更大的类型如long long。例如// 埃氏筛中 for (long long j (long long)i * i; j N; j i) { isPrime[j] false; } // 线性筛中 long long composite (long long)i * primes[j]; if (composite N) break; // 也可以作为内层循环条件的一部分 isPrime[composite] false;这里的类型转换(long long)i * i非常重要它确保了乘法运算在long long类型中进行。如果写成i * i即使左边用long long j接收乘法本身已经在int中溢出结果已经是错的了。4. 三种筛法的C实现与对比下面给出三种筛法的完整、健壮的C实现代码并附上详细注释。4.1 普通筛法实现#include iostream #include vector #include cmath using namespace std; void normalSieve(int N) { vectorbool isPrime(N 1, true); // 默认所有数都是质数 isPrime[0] isPrime[1] false; // 0和1不是质数 for (int i 2; i N; i) { if (isPrime[i]) { // 将i的倍数全部标记为合数 // 注意这里即使用i是合数也会执行标记这是它低效的原因 for (long long j (long long)i * 2; j N; j i) { isPrime[j] false; } } } // 输出结果 cout 普通筛法质数列表 (N N ): endl; int count 0; for (int i 2; i N; i) { if (isPrime[i]) { count; // 为了输出整洁每行打印10个 cout i \t; if (count % 10 0) cout endl; } } cout \n总计: count 个质数。 endl; }4.2 埃氏筛法实现优化版void eratosthenesSieve(int N) { vectorbool isPrime(N 1, true); isPrime[0] isPrime[1] false; // 优化1外层i只需遍历到 sqrt(N) for (int i 2; (long long)i * i N; i) { if (isPrime[i]) { // 优化2内层j从 i*i 开始 for (long long j (long long)i * i; j N; j i) { isPrime[j] false; } } } // 收集并输出质数 cout \n埃氏筛法质数列表 (N N ): endl; vectorint primes; for (int i 2; i N; i) { if (isPrime[i]) { primes.push_back(i); } } int count 0; for (int prime : primes) { count; cout prime \t; if (count % 10 0) cout endl; } cout \n总计: primes.size() 个质数。 endl; }4.3 线性筛法欧拉筛实现void eulerSieve(int N) { vectorbool isPrime(N 1, true); vectorint primes; // 用于存储已找到的质数 isPrime[0] isPrime[1] false; for (int i 2; i N; i) { if (isPrime[i]) { primes.push_back(i); // i是质数加入列表 } // 遍历当前已找到的所有质数 for (int j 0; j (int)primes.size(); j) { long long composite (long long)i * primes[j]; if (composite N) { break; // 生成的合数超过范围跳出内层循环 } isPrime[composite] false; // 标记合数 // 核心保证每个合数只被最小质因子筛一次 if (i % primes[j] 0) { break; } } } // 输出结果 cout \n线性筛法质数列表 (N N ): endl; int count 0; for (int prime : primes) { count; cout prime \t; if (count % 10 0) cout endl; } cout \n总计: primes.size() 个质数。 endl; }4.4 性能对比与测试我们可以写一个简单的main函数来测试和对比。#include chrono int main() { int N 1000000; // 测试范围1到100万 auto start chrono::high_resolution_clock::now(); // normalSieve(N); // 普通筛法较慢测试小N即可如100000 auto end chrono::high_resolution_clock::now(); chrono::durationdouble elapsed end - start; // cout 普通筛法耗时: elapsed.count() 秒 endl; start chrono::high_resolution_clock::now(); eratosthenesSieve(N); end chrono::high_resolution_clock::now(); elapsed end - start; cout 埃氏筛法耗时: elapsed.count() 秒 endl; start chrono::high_resolution_clock::now(); eulerSieve(N); end chrono::high_resolution_clock::now(); elapsed end - start; cout 线性筛法耗时: elapsed.count() 秒 endl; return 0; }在我的测试环境普通家用PC下N1,000,000时的近似结果埃氏筛法约 0.015 秒线性筛法约 0.010 秒对比分析时间复杂度普通筛 O(N log log N)埃氏筛 O(N log log N)线性筛 O(N)。理论上线性筛最优。实际性能当N在10^6~10^7量级时优化良好的埃氏筛和线性筛速度相差不大甚至有时埃氏筛因缓存友好性更佳而略快。因为埃氏筛的内层循环是连续的加法操作对CPU缓存非常友好。而线性筛的内层循环需要频繁访问primes向量和进行取模运算常数因子可能更大。绝对优势区间当N非常大比如超过10^8时线性筛的O(N)复杂度优势才会明显体现出来。同时线性筛在筛的过程中天然地得到了有序的质数列表存储在primes中这是埃氏筛需要额外循环收集才能得到的。空间复杂度三者都是 O(N)用于存储布尔标记数组。5. 常见问题与排查技巧实录在实际编码和解题中你会遇到各种各样的问题。下面是我总结的一些典型“坑”和解决思路。5.1 程序运行缓慢或超时问题现象在OJ上提交代码判定为“Time Limit Exceeded”(TLE)。排查步骤检查算法选择你是否错误地使用了“试除法”来求解范围内的所有质数对于N10^5的情况必须使用筛法。检查是否为优化后的埃氏筛或线性筛确认埃氏筛的外层循环是否只到sqrt(N)内层循环是否从i*i开始线性筛的break条件是否正确检查输入范围N是否使用了int导致溢出循环条件是否因溢出变成死循环务必使用long long进行乘法运算和比较。检查输出如果题目要求输出大量质数cout可能成为瓶颈。可以尝试使用printf或者用\n代替endlendl会刷新缓冲区更慢。在竞赛中有时需要关闭C输入输出流同步来加速ios::sync_with_stdio(false); cin.tie(nullptr);。5.2 程序输出错误或崩溃问题现象输出结果不对或者直接“Runtime Error”(RE)。排查步骤数组越界这是最常见的原因。检查你的isPrime数组大小是否是N1在内层标记循环中是否保证了j N在线性筛中是否在判断composite N后及时break初始化错误是否忘记了将isPrime[0]和isPrime[1]设置为false逻辑错误在线性筛中最易错的就是if (i % primes[j] 0) break;这行代码的位置。它必须放在标记合数isPrime[composite] false;之后。顺序错了就会导致某些合数未被标记。数据类型错误vectorbool的下标访问是没问题的但如果你错误地使用了vectorint并试图用int当布尔值用可能会出问题。坚持使用vectorbool。5.3 内存超限问题现象“Memory Limit Exceeded”(MLE)。排查步骤确认使用了vectorbool这是最省内存的存储方式。如果用了vectorchar或vectorint内存会大8倍或32倍。估算内存使用vectorbool(N1)大约占用(N1)/8字节。对于N10^8约需要12.5MB内存这在大多数256MB内存限制的OJ中是可行的。如果N更大可能需要考虑分段筛Segmented Sieve这是一种更高级的技术可以只保留一小段范围的标记数组在内存中。5.4 线性筛理解不透彻困惑点为什么i要从2遍历到N即使i是合数也要遍历解释在线性筛中i的角色是“倍数因子”。合数i本身虽然已被标记但它需要参与生成那些以它为倍数的、更大的合数。例如当i4时质数列表里有[2,3]。我们用4*28标记了8然后因为4%20而break。如果我们因为i4是合数就跳过它那么合数8就无法被标记因为i8时质数列表里第一个质数是28*216N?不一定但更重要的是8的最小质因子是2本应由i4和prime2这个组合来筛掉。所以i必须遍历每一个数。6. 进阶应用与扩展思考掌握了基础的质数筛我们可以解决更多有趣的问题。6.1 筛法求最小质因子线性筛的一个强大扩展是可以在筛的过程中记录每个数的最小质因子Least Prime Factor, LPF。只需稍作修改vectorint lpf(N 1, 0); // 0表示质数或未处理 vectorint primes; for (int i 2; i N; i) { if (lpf[i] 0) { // i是质数 lpf[i] i; primes.push_back(i); } for (int p : primes) { if (p lpf[i] || (long long)i * p N) break; int composite i * p; lpf[composite] p; // 记录合数的最小质因子 } }有了LPF数组我们可以用O(log n)的时间对任意数进行质因数分解这在解决数论问题时非常高效。6.2 筛法求欧拉函数欧拉函数 φ(n) 表示小于等于n的正整数中与n互质的数的个数。利用线性筛和最小质因子的信息可以在O(N)时间内预处理出1到N所有数的欧拉函数值。vectorint phi(N 1); vectorbool isPrime(N 1, true); vectorint primes; phi[1] 1; for (int i 2; i N; i) { if (isPrime[i]) { primes.push_back(i); phi[i] i - 1; // 质数的欧拉函数值为i-1 } for (int p : primes) { if ((long long)i * p N) break; isPrime[i * p] false; if (i % p 0) { phi[i * p] phi[i] * p; // 情况1p是i的质因子 break; } else { phi[i * p] phi[i] * (p - 1); // 情况2p与i互质 } } }6.3 如何选择用哪种筛法根据我的经验可以遵循以下原则教学或理解原理从普通筛法开始理解筛的思想然后学习埃氏筛理解优化最后攻克线性筛掌握其精妙之处。竞赛或快速开发首选埃氏筛。它代码简单不易写错在数据范围N≤10^7内效率足够且缓存友好。除非题目明确要求O(N)复杂度或者需要利用线性筛的副产品如质数列表、最小质因子、欧拉函数否则埃氏筛是性价比最高的选择。极致性能与超大范围当N超过10^8或者需要同时计算多个积性函数如欧拉函数、莫比乌斯函数时使用线性筛。它的理论复杂度最优且功能强大。质数筛是算法工具箱里的一把利器。理解它、熟练运用它不仅能帮你解决具体的质数问题更能让你深刻体会到“以空间换时间”和“避免重复计算”这两大算法核心思想。多写几遍代码多尝试用不同的N去测试感受它们性能的差异遇到问题时回头来再看看原理。当你能够不假思索地写出正确高效的筛法代码时你对循环、条件判断、数组等基础编程概念的理解也一定上了一个新台阶。
