1. 项目概述为什么“筛选法”是求素数的利器在C编程和算法学习的路上求素数是一个绕不开的经典问题。无论是刚入门的新手还是准备面试的求职者都会被问到“如何高效地找出一定范围内的所有素数”。最直观的想法可能是对每个数n用2到√n之间的所有整数去试除这就是“试除法”。这个方法简单易懂但当范围一大比如要找出100万以内的所有素数它的效率就捉襟见肘了。这时“筛选法”就闪亮登场了。它不是一个单一的算法而是一类算法的统称核心思想不是去“判断”一个数是不是素数而是主动“筛掉”那些肯定不是素数的合数剩下的自然就是素数。这种方法效率极高是处理大规模素数问题的标准答案。今天我们就来彻底拆解用C实现筛选法的方方面面从最经典的埃拉托斯特尼筛法简称埃氏筛到其优化版本再到理论极限的欧拉筛我会结合我多年写算法和性能调优的经验把原理、代码、坑点以及性能对比一次讲透。2. 算法核心原理与演进从埃氏筛到欧拉筛2.1 埃拉托斯特尼筛法古老而经典的思想埃氏筛法的思想非常直观其历史可以追溯到古希腊。我们想找出所有小于等于N的素数。首先假设所有数从2开始都是潜在的素数。然后我们从最小的素数2开始将其所有的倍数4, 6, 8, …标记为非素数合数。接着找到下一个未被标记的数此时是3它一定是素数因为所有小于它的数的倍数都已被处理它没被筛掉然后筛去3的所有倍数。如此反复直到我们处理的数大于√N为止。为什么是√N因为如果一个数N是合数那么它必然有一个因子小于等于√N。所以所有小于等于N的合数必然会被某个小于等于√N的素数筛掉。这个算法的C实现骨架非常清晰创建一个布尔数组isPrime[0..N]初始全部设为true表示都是素数。将isPrime[0]和isPrime[1]设为false0和1不是素数。从i 2开始循环到sqrt(N)如果isPrime[i]为true则i是素数。然后从j i * i开始以i为步长递增直到超过N将isPrime[j]设为false。这里从i*i开始筛是因为像2*i,3*i, …,(i-1)*i这些数已经在之前被更小的素数2, 3, …, i-1筛过了重复筛除浪费计算。注意这里有一个初学者常犯的“坑”。循环终止条件写成i sqrt(N)在每次循环时都会计算一次sqrt(N)这是一个相对耗时的操作。更高效的做法是在循环外计算int limit sqrt(N)或者直接写成i * i N。后者避免了浮点数运算和函数调用在性能敏感的场合是更好的选择。2.2 埃氏筛的优化细节处的性能提升基础的埃氏筛已经很快但我们还能从两个细节上压榨性能。优化一只筛奇数。除了2以外所有的偶数都不可能是素数。我们可以利用这一点将数组大小减半只处理奇数。具体做法是创建一个大小为(N1)/2的布尔数组其中下标i对应原始的数字num 2*i 1。这样我们初始化时只需要把数组全部设为true然后从奇数3开始筛对应下标i1。在筛除倍数时步长也要相应调整。例如对于素数p奇数它的奇数倍p * k只有当k也是奇数时才是奇数需要被筛。但更通用的做法是我们只关心在“奇数数组”中如何定位。一个常见的技巧是对于素数p从p*p开始筛但p*p一定是奇数奇数乘奇数我们在奇数数组中找到它的位置index (p*p) / 2然后以步长p注意不是2*p进行筛除。因为p是奇数p 2p 3p是奇数p 4p 5p是奇数……实际上步长应该是2*p才能保证每次都跳到奇数的倍数上。这里有点绕我建议在代码中通过实际数字推演一下。这个优化能减少近一半的内存访问和赋值操作效果显著。优化二使用vectorbool的特化。C标准库为vectorbool提供了空间特化它通常用一个比特bit而不是一个字节byte来存储一个布尔值。这意味着内存占用可以减少到原来的1/8。对于需要处理数千万甚至上亿级别范围的筛法这个内存节省是巨大的。但要注意vectorbool因为不是标准的容器它打包存储所以某些操作如取迭代器指向的元素的引用行为特殊但在筛法这种顺序访问、只做赋值的场景下它是完美适用的。使用bitset编译期大小固定或手动进行位操作是更极致的优化但vectorbool在易用性和性能之间取得了很好的平衡。2.3 欧拉筛理论上的线性时间复杂度埃氏筛即使经过优化一个合数仍然可能被多个素数重复筛除例如合数30会被素数2、3、5各筛一次。欧拉筛也称线性筛的核心改进就是确保每个合数只被它的最小质因子筛掉一次从而将时间复杂度降到真正的O(N)。其算法流程如下同样维护一个布尔数组isPrime和一个记录素数的数组primes。从2开始遍历到N。如果当前数字i是素数isPrime[i] true就把它加入primes数组。无论i是不是素数都遍历已知的素数列表primes记为p a. 计算合数n i * p。 b. 如果n超过N跳出循环。 c. 将isPrime[n]标记为false。 d.关键步骤如果i能被当前素数p整除即i % p 0则跳出素数遍历循环。这是保证每个合数只被筛一次的灵魂所在。为什么这个break如此关键我们来看一个例子。假设i 4已知素数primes [2, 3]。第一轮p2筛掉合数4*28。此时i % p 04%20跳出循环。如果不跳出下一轮p3会筛掉4*312。但请注意12的最小质因子是2它本应该在未来当i6时被p2筛掉6*212。现在被i4和p3筛掉就导致了重复筛除。更重要的是这破坏了“仅被最小质因子筛除”的约定。当i % p 0时说明p是i的最小质因子因为我们是按顺序遍历素数的。那么对于下一个素数p_next要筛的合数i * p_next的最小质因子应该是p而不是p_next因为i里已经包含质因子p。所以为了保证每个合数x只在i x / min_prime_factor(x)时被筛除我们必须在此刻跳出。欧拉筛的实现比埃氏筛稍复杂但理解了其核心原理后代码写起来并不难。它的最大优势是线性复杂度在处理极端大的N时理论性能更优。但在实际运行中由于常数因子较大需要维护素数列表和更多的模运算在N不是特别大比如几千万以内时优化后的埃氏筛可能因为缓存友好、操作简单而跑得更快。3. C实现详解与代码剖析3.1 基础埃氏筛实现我们先从一个最基础、最易懂的版本开始。这个版本使用了vectorbool并采用了i*i N的循环条件。#include iostream #include vector #include cmath void eratosthenesSieve(int n) { if (n 2) return; std::vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; // 0和1不是素数 for (int i 2; i * i n; i) { if (isPrime[i]) { // 从 i*i 开始因为更小的倍数已被更小的素数筛过 for (int j i * i; j n; j i) { isPrime[j] false; } } } // 输出结果或进行其他处理 std::cout Primes up to n :\n; for (int i 2; i n; i) { if (isPrime[i]) { std::cout i ; } } std::cout std::endl; } int main() { int limit 100; eratosthenesSieve(limit); return 0; }代码要点解析vectorbool isPrime(n1, true)创建大小为n1的布尔向量并初始化为true。这里n1是为了让下标直接对应数字方便理解。i * i n这是循环的关键条件。它等价于i sqrt(n)但避免了浮点数运算和函数调用效率更高。内层循环for (int j i * i; j n; j i)这是筛除动作。从i*i开始能避免重复筛除是埃氏筛的标准写法。步长为i即筛除i的所有倍数。内存与性能这个版本在处理很大的n例如1亿时vectorbool会占用大约12.5MB的内存1亿 bits ≈ 12.5 MB这是可以接受的。主要耗时在内层循环的赋值操作上。3.2 优化版埃氏筛奇数筛与位压缩接下来我们实现优化版本只处理奇数并显式使用位运算来模拟vectorbool的行为以获得最大程度的控制权和性能。#include iostream #include vector #include cmath void optimizedEratosthenesSieve(int n) { if (n 2) return; // 只处理奇数数组大小减半 // isPrimeBit[i] 对应数字 num 2*i 1 int size (n 1) / 2; std::vectorbool isPrimeBit(size, true); // 单独处理素数2 std::cout 2 ; // 从3开始对应下标 i1 (3 2*11) // 循环条件num 2*i1 sqrt(n) - i (sqrt(n)-1)/2 int sqrt_limit static_castint(std::sqrt(n)); for (int i 1; 2 * i 1 sqrt_limit; i) { if (isPrimeBit[i]) { int prime 2 * i 1; // 当前素数 // 筛除从 prime*prime 开始的所有奇数倍 // prime*prime 是奇数其下标 startIndex (prime*prime) / 2 // 但 prime*prime 可能很大需要确保计算在int范围内 long long start static_castlong long(prime) * prime; if (start n) continue; int startIndex (start) / 2; // 步长prime 的奇数倍间隔是 2*prime // 在奇数数组中步长对应的下标增量是 prime (因为 2*prime / 2 prime) for (int j startIndex; j size; j prime) { isPrimeBit[j] false; } } } // 输出结果 for (int i 1; i size; i) { if (isPrimeBit[i]) { std::cout (2 * i 1) ; } } std::cout std::endl; } int main() { int limit 100; optimizedEratosthenesSieve(limit); return 0; }优化点与注意事项奇数映射num 2*i 1。所有偶数除了2都被天然排除在外。下标计算素数prime对应的下标是i (prime-1)/2。合数composite的下标是j composite/2因为composite是奇数。起始点从prime*prime开始筛。这里使用long long防止乘法溢出这是一个非常重要的细节当prime较大时比如大于46340prime*prime可能超过32位int的范围。步长在原始数字空间我们筛除prime, 3*prime, 5*prime, ...这些数都是奇数它们之间的差是2*prime。映射到奇数数组下标差就是(2*prime)/2 prime。所以内层循环的步长是prime。性能提升这个版本将内存需求减半循环次数也大幅减少。在实际测试中对于上亿的数据范围其运行时间通常比基础版快30%-50%。3.3 欧拉筛实现最后我们实现时间复杂度为O(N)的欧拉筛。#include iostream #include vector void eulerSieve(int n) { if (n 2) return; std::vectorbool isPrime(n 1, true); std::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 primes.size() i * primes[j] n; j) { isPrime[i * primes[j]] false; // 筛除合数 i * primes[j] // 关键如果i能被当前素数整除则跳出循环 if (i % primes[j] 0) { break; } } } // 输出结果 std::cout Primes up to n :\n; for (int prime : primes) { std::cout prime ; } std::cout std::endl; } int main() { int limit 100; eulerSieve(limit); return 0; }欧拉筛核心解析外层循环i从2遍历到N。i在这里的角色是“倍数因子”。素数判定与收集如果isPrime[i]为真则i是素数加入primes列表。注意这个判定发生在遍历素数列表之前。这意味着当我们用i和素数列表去筛合数时i本身可能刚刚被确认为素数。内层循环遍历所有已知素数primes[j]并筛除合数i * primes[j]。循环条件有两个素数索引不越界且合数不超过N。灵魂breakif (i % primes[j] 0) break;。这是保证线性复杂度的关键。当i能被primes[j]整除时说明primes[j]是i的最小质因子因为primes列表是递增的。那么对于下一个素数primes[j1]合数i * primes[j1]的最小质因子应该是primes[j]而不是primes[j1]。如果继续筛这个合数会在未来i (i / primes[j]) * primes[j1]时被primes[j]再次筛除造成重复。因此必须跳出。内存与性能欧拉筛需要额外的primes数组来存储素数内存开销略大于埃氏筛。其内层循环包含一个模运算 (%)这是一个相对较慢的操作。因此虽然其时间复杂度是线性的但常数项较大。在N小于一定规模例如5000万时优化后的埃氏筛可能在实际运行时间上更有优势。4. 性能对比与实战选择纸上得来终觉浅绝知此事要躬行。理论分析之后我们必须在实际的代码运行中感受差异。我写了一个简单的性能测试框架在同一台机器上使用相同的编译优化选项-O2分别测试三个算法在寻找N100,000,000一亿以内素数时的表现。测试环境概要CPU为现代x86处理器编译器为GCC 11.2编译选项-O2 -marchnative。测试结果仅供参考具体时间因硬件而异算法运行时间秒内存占用约特点基础埃氏筛~1.8s12.5 MB实现简单易于理解优化埃氏筛奇数位~1.1s6.25 MB内存和速度均有显著优化欧拉筛~2.3s12.5 MB 素数列表理论复杂度最优但常数大结果分析优化埃氏筛胜出在这个规模1亿下优化后的埃氏筛凭借其简洁的操作主要是赋值和良好的缓存局部性连续内存访问跑得最快。内存占用也只有一半。欧拉筛的劣势欧拉筛的模运算 (%) 和更多的条件判断增加了每个操作的开销。虽然它遍历的总次数是O(N)但每个操作的成本比埃氏筛的简单赋值高。因此在N不是大到一定程度时其常数因子抵消了复杂度优势。基础埃氏筛居中作为基准它比欧拉筛快但比优化版慢。实操心得在绝大多数编程竞赛和日常应用中当N在10^7一千万到10^8一亿量级时优化后的埃氏筛是首选。它实现了速度、内存和代码复杂度的最佳平衡。只有当N极大例如超过10^9并且你对性能有极致要求愿意为可能的内存分块和更复杂的优化付出代价时才需要深入考虑欧拉筛的进一步优化变种。如何选择教学与理解从基础埃氏筛开始理解筛法的思想。竞赛与面试掌握优化埃氏筛和欧拉筛的原理与实现并能解释其区别。通常写优化埃氏筛就足够了。极端性能需求考虑欧拉筛并可能结合分块筛法Segmented Sieve来处理无法一次性装入内存的超大范围。5. 常见问题与排查技巧实录在实际实现和使用筛法时你肯定会遇到一些“坑”。下面是我总结的常见问题及解决方法。5.1 数组越界与溢出这是最常出现的两类运行时错误。问题1内层循环起始点i*i导致整数溢出。// 错误示例 for (int i 2; i * i n; i) { // 当i较大时i*i可能溢出 for (int j i * i; j n; j i) { // j的初始值i*i已溢出行为未定义 // ... } }解决方案将循环变量或乘法结果升级到更宽的类型如long long。for (long long i 2; i * i n; i) { for (long long j i * i; j n; j i) { // ... } } // 或者更高效地在循环外计算上限 int limit sqrt(n); // 或使用 (int)sqrt((double)n) for (int i 2; i limit; i) { // ... }问题2优化筛中prime*prime或下标计算溢出。在优化埃氏筛中prime是int但prime*prime很容易超过int范围。必须使用long long进行计算和比较。long long start static_castlong long(prime) * prime; if (start n) continue; int startIndex start / 2; // 注意start是long long但除法后赋值给int5.2 性能陷阱陷阱1在循环条件中重复计算sqrt(n)。for (int i 2; i sqrt(n); i) { // 每次循环都计算sqrt慢解决在循环前计算一次。int limit static_castint(std::sqrt(n)); for (int i 2; i limit; i) {陷阱2使用vectorint或普通数组存储布尔值。一个bool在C中通常占1字节而一个int占4字节。使用vectorint会浪费4倍内存降低缓存效率。务必使用vectorbool或bitset。陷阱3输出操作耗时。如果你的目的是计算素数个数或进行后续处理在性能测试时避免将大量素数输出到控制台。cout输出是极其缓慢的。可以改为计数或写入文件进行测试。5.3 算法正确性验证如何确保你写的筛法是正确的对于小范围N可以用最笨的试除法进行交叉验证。bool isPrimeTrial(int num) { if (num 2) return false; for (int i 2; i * i num; i) { if (num % i 0) return false; } return true; } void validateSieve(const std::vectorbool isPrime, int n) { for (int i 0; i n; i) { bool sieveResult isPrime[i]; bool trialResult isPrimeTrial(i); if (sieveResult ! trialResult) { std::cerr Mismatch at i : Sieve sieveResult , Trial trialResult std::endl; } } std::cout Validation passed (if no errors above). std::endl; }在开发阶段用这个函数验证你的筛法结果可以快速定位逻辑错误比如下标映射错误、循环条件错误等。5.4 内存与规模限制当N非常大例如10亿时即使使用vectorbool约120MB内存也可能成为问题。这时需要采用分段筛法。 分段筛法的思想是将区间[2, N]分成若干个小段每次只将当前段加载到内存中进行筛除。它需要预先筛出√N以内的素数称为“基础素数”然后用这些素数去筛每一个小段。其核心代码结构如下用普通筛法找出sqrt(N)以内的所有素数存储在basePrimes中。将[2, N]划分为长度为SEG_SIZE的段如[2, SEG_SIZE],[SEG_SIZE1, 2*SEG_SIZE], …。对于每一段[low, high]创建一个布尔数组segment大小为high-low1初始为true。对于每个基础素数p找到段内第一个能被p整除的数start max(p*p, ((low p - 1) / p) * p)。从start开始以p为步长将segment[start-low],segment[start-lowp], … 标记为false。处理完所有基础素数后segment中为true的位置对应的数字lowindex就是该段内的素数。分段筛法将内存需求从O(N)降到了O(√N SEG_SIZE)是处理海量数据的关键技术。
C++素数筛选算法：从埃氏筛到欧拉筛的原理、实现与性能优化
1. 项目概述为什么“筛选法”是求素数的利器在C编程和算法学习的路上求素数是一个绕不开的经典问题。无论是刚入门的新手还是准备面试的求职者都会被问到“如何高效地找出一定范围内的所有素数”。最直观的想法可能是对每个数n用2到√n之间的所有整数去试除这就是“试除法”。这个方法简单易懂但当范围一大比如要找出100万以内的所有素数它的效率就捉襟见肘了。这时“筛选法”就闪亮登场了。它不是一个单一的算法而是一类算法的统称核心思想不是去“判断”一个数是不是素数而是主动“筛掉”那些肯定不是素数的合数剩下的自然就是素数。这种方法效率极高是处理大规模素数问题的标准答案。今天我们就来彻底拆解用C实现筛选法的方方面面从最经典的埃拉托斯特尼筛法简称埃氏筛到其优化版本再到理论极限的欧拉筛我会结合我多年写算法和性能调优的经验把原理、代码、坑点以及性能对比一次讲透。2. 算法核心原理与演进从埃氏筛到欧拉筛2.1 埃拉托斯特尼筛法古老而经典的思想埃氏筛法的思想非常直观其历史可以追溯到古希腊。我们想找出所有小于等于N的素数。首先假设所有数从2开始都是潜在的素数。然后我们从最小的素数2开始将其所有的倍数4, 6, 8, …标记为非素数合数。接着找到下一个未被标记的数此时是3它一定是素数因为所有小于它的数的倍数都已被处理它没被筛掉然后筛去3的所有倍数。如此反复直到我们处理的数大于√N为止。为什么是√N因为如果一个数N是合数那么它必然有一个因子小于等于√N。所以所有小于等于N的合数必然会被某个小于等于√N的素数筛掉。这个算法的C实现骨架非常清晰创建一个布尔数组isPrime[0..N]初始全部设为true表示都是素数。将isPrime[0]和isPrime[1]设为false0和1不是素数。从i 2开始循环到sqrt(N)如果isPrime[i]为true则i是素数。然后从j i * i开始以i为步长递增直到超过N将isPrime[j]设为false。这里从i*i开始筛是因为像2*i,3*i, …,(i-1)*i这些数已经在之前被更小的素数2, 3, …, i-1筛过了重复筛除浪费计算。注意这里有一个初学者常犯的“坑”。循环终止条件写成i sqrt(N)在每次循环时都会计算一次sqrt(N)这是一个相对耗时的操作。更高效的做法是在循环外计算int limit sqrt(N)或者直接写成i * i N。后者避免了浮点数运算和函数调用在性能敏感的场合是更好的选择。2.2 埃氏筛的优化细节处的性能提升基础的埃氏筛已经很快但我们还能从两个细节上压榨性能。优化一只筛奇数。除了2以外所有的偶数都不可能是素数。我们可以利用这一点将数组大小减半只处理奇数。具体做法是创建一个大小为(N1)/2的布尔数组其中下标i对应原始的数字num 2*i 1。这样我们初始化时只需要把数组全部设为true然后从奇数3开始筛对应下标i1。在筛除倍数时步长也要相应调整。例如对于素数p奇数它的奇数倍p * k只有当k也是奇数时才是奇数需要被筛。但更通用的做法是我们只关心在“奇数数组”中如何定位。一个常见的技巧是对于素数p从p*p开始筛但p*p一定是奇数奇数乘奇数我们在奇数数组中找到它的位置index (p*p) / 2然后以步长p注意不是2*p进行筛除。因为p是奇数p 2p 3p是奇数p 4p 5p是奇数……实际上步长应该是2*p才能保证每次都跳到奇数的倍数上。这里有点绕我建议在代码中通过实际数字推演一下。这个优化能减少近一半的内存访问和赋值操作效果显著。优化二使用vectorbool的特化。C标准库为vectorbool提供了空间特化它通常用一个比特bit而不是一个字节byte来存储一个布尔值。这意味着内存占用可以减少到原来的1/8。对于需要处理数千万甚至上亿级别范围的筛法这个内存节省是巨大的。但要注意vectorbool因为不是标准的容器它打包存储所以某些操作如取迭代器指向的元素的引用行为特殊但在筛法这种顺序访问、只做赋值的场景下它是完美适用的。使用bitset编译期大小固定或手动进行位操作是更极致的优化但vectorbool在易用性和性能之间取得了很好的平衡。2.3 欧拉筛理论上的线性时间复杂度埃氏筛即使经过优化一个合数仍然可能被多个素数重复筛除例如合数30会被素数2、3、5各筛一次。欧拉筛也称线性筛的核心改进就是确保每个合数只被它的最小质因子筛掉一次从而将时间复杂度降到真正的O(N)。其算法流程如下同样维护一个布尔数组isPrime和一个记录素数的数组primes。从2开始遍历到N。如果当前数字i是素数isPrime[i] true就把它加入primes数组。无论i是不是素数都遍历已知的素数列表primes记为p a. 计算合数n i * p。 b. 如果n超过N跳出循环。 c. 将isPrime[n]标记为false。 d.关键步骤如果i能被当前素数p整除即i % p 0则跳出素数遍历循环。这是保证每个合数只被筛一次的灵魂所在。为什么这个break如此关键我们来看一个例子。假设i 4已知素数primes [2, 3]。第一轮p2筛掉合数4*28。此时i % p 04%20跳出循环。如果不跳出下一轮p3会筛掉4*312。但请注意12的最小质因子是2它本应该在未来当i6时被p2筛掉6*212。现在被i4和p3筛掉就导致了重复筛除。更重要的是这破坏了“仅被最小质因子筛除”的约定。当i % p 0时说明p是i的最小质因子因为我们是按顺序遍历素数的。那么对于下一个素数p_next要筛的合数i * p_next的最小质因子应该是p而不是p_next因为i里已经包含质因子p。所以为了保证每个合数x只在i x / min_prime_factor(x)时被筛除我们必须在此刻跳出。欧拉筛的实现比埃氏筛稍复杂但理解了其核心原理后代码写起来并不难。它的最大优势是线性复杂度在处理极端大的N时理论性能更优。但在实际运行中由于常数因子较大需要维护素数列表和更多的模运算在N不是特别大比如几千万以内时优化后的埃氏筛可能因为缓存友好、操作简单而跑得更快。3. C实现详解与代码剖析3.1 基础埃氏筛实现我们先从一个最基础、最易懂的版本开始。这个版本使用了vectorbool并采用了i*i N的循环条件。#include iostream #include vector #include cmath void eratosthenesSieve(int n) { if (n 2) return; std::vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; // 0和1不是素数 for (int i 2; i * i n; i) { if (isPrime[i]) { // 从 i*i 开始因为更小的倍数已被更小的素数筛过 for (int j i * i; j n; j i) { isPrime[j] false; } } } // 输出结果或进行其他处理 std::cout Primes up to n :\n; for (int i 2; i n; i) { if (isPrime[i]) { std::cout i ; } } std::cout std::endl; } int main() { int limit 100; eratosthenesSieve(limit); return 0; }代码要点解析vectorbool isPrime(n1, true)创建大小为n1的布尔向量并初始化为true。这里n1是为了让下标直接对应数字方便理解。i * i n这是循环的关键条件。它等价于i sqrt(n)但避免了浮点数运算和函数调用效率更高。内层循环for (int j i * i; j n; j i)这是筛除动作。从i*i开始能避免重复筛除是埃氏筛的标准写法。步长为i即筛除i的所有倍数。内存与性能这个版本在处理很大的n例如1亿时vectorbool会占用大约12.5MB的内存1亿 bits ≈ 12.5 MB这是可以接受的。主要耗时在内层循环的赋值操作上。3.2 优化版埃氏筛奇数筛与位压缩接下来我们实现优化版本只处理奇数并显式使用位运算来模拟vectorbool的行为以获得最大程度的控制权和性能。#include iostream #include vector #include cmath void optimizedEratosthenesSieve(int n) { if (n 2) return; // 只处理奇数数组大小减半 // isPrimeBit[i] 对应数字 num 2*i 1 int size (n 1) / 2; std::vectorbool isPrimeBit(size, true); // 单独处理素数2 std::cout 2 ; // 从3开始对应下标 i1 (3 2*11) // 循环条件num 2*i1 sqrt(n) - i (sqrt(n)-1)/2 int sqrt_limit static_castint(std::sqrt(n)); for (int i 1; 2 * i 1 sqrt_limit; i) { if (isPrimeBit[i]) { int prime 2 * i 1; // 当前素数 // 筛除从 prime*prime 开始的所有奇数倍 // prime*prime 是奇数其下标 startIndex (prime*prime) / 2 // 但 prime*prime 可能很大需要确保计算在int范围内 long long start static_castlong long(prime) * prime; if (start n) continue; int startIndex (start) / 2; // 步长prime 的奇数倍间隔是 2*prime // 在奇数数组中步长对应的下标增量是 prime (因为 2*prime / 2 prime) for (int j startIndex; j size; j prime) { isPrimeBit[j] false; } } } // 输出结果 for (int i 1; i size; i) { if (isPrimeBit[i]) { std::cout (2 * i 1) ; } } std::cout std::endl; } int main() { int limit 100; optimizedEratosthenesSieve(limit); return 0; }优化点与注意事项奇数映射num 2*i 1。所有偶数除了2都被天然排除在外。下标计算素数prime对应的下标是i (prime-1)/2。合数composite的下标是j composite/2因为composite是奇数。起始点从prime*prime开始筛。这里使用long long防止乘法溢出这是一个非常重要的细节当prime较大时比如大于46340prime*prime可能超过32位int的范围。步长在原始数字空间我们筛除prime, 3*prime, 5*prime, ...这些数都是奇数它们之间的差是2*prime。映射到奇数数组下标差就是(2*prime)/2 prime。所以内层循环的步长是prime。性能提升这个版本将内存需求减半循环次数也大幅减少。在实际测试中对于上亿的数据范围其运行时间通常比基础版快30%-50%。3.3 欧拉筛实现最后我们实现时间复杂度为O(N)的欧拉筛。#include iostream #include vector void eulerSieve(int n) { if (n 2) return; std::vectorbool isPrime(n 1, true); std::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 primes.size() i * primes[j] n; j) { isPrime[i * primes[j]] false; // 筛除合数 i * primes[j] // 关键如果i能被当前素数整除则跳出循环 if (i % primes[j] 0) { break; } } } // 输出结果 std::cout Primes up to n :\n; for (int prime : primes) { std::cout prime ; } std::cout std::endl; } int main() { int limit 100; eulerSieve(limit); return 0; }欧拉筛核心解析外层循环i从2遍历到N。i在这里的角色是“倍数因子”。素数判定与收集如果isPrime[i]为真则i是素数加入primes列表。注意这个判定发生在遍历素数列表之前。这意味着当我们用i和素数列表去筛合数时i本身可能刚刚被确认为素数。内层循环遍历所有已知素数primes[j]并筛除合数i * primes[j]。循环条件有两个素数索引不越界且合数不超过N。灵魂breakif (i % primes[j] 0) break;。这是保证线性复杂度的关键。当i能被primes[j]整除时说明primes[j]是i的最小质因子因为primes列表是递增的。那么对于下一个素数primes[j1]合数i * primes[j1]的最小质因子应该是primes[j]而不是primes[j1]。如果继续筛这个合数会在未来i (i / primes[j]) * primes[j1]时被primes[j]再次筛除造成重复。因此必须跳出。内存与性能欧拉筛需要额外的primes数组来存储素数内存开销略大于埃氏筛。其内层循环包含一个模运算 (%)这是一个相对较慢的操作。因此虽然其时间复杂度是线性的但常数项较大。在N小于一定规模例如5000万时优化后的埃氏筛可能在实际运行时间上更有优势。4. 性能对比与实战选择纸上得来终觉浅绝知此事要躬行。理论分析之后我们必须在实际的代码运行中感受差异。我写了一个简单的性能测试框架在同一台机器上使用相同的编译优化选项-O2分别测试三个算法在寻找N100,000,000一亿以内素数时的表现。测试环境概要CPU为现代x86处理器编译器为GCC 11.2编译选项-O2 -marchnative。测试结果仅供参考具体时间因硬件而异算法运行时间秒内存占用约特点基础埃氏筛~1.8s12.5 MB实现简单易于理解优化埃氏筛奇数位~1.1s6.25 MB内存和速度均有显著优化欧拉筛~2.3s12.5 MB 素数列表理论复杂度最优但常数大结果分析优化埃氏筛胜出在这个规模1亿下优化后的埃氏筛凭借其简洁的操作主要是赋值和良好的缓存局部性连续内存访问跑得最快。内存占用也只有一半。欧拉筛的劣势欧拉筛的模运算 (%) 和更多的条件判断增加了每个操作的开销。虽然它遍历的总次数是O(N)但每个操作的成本比埃氏筛的简单赋值高。因此在N不是大到一定程度时其常数因子抵消了复杂度优势。基础埃氏筛居中作为基准它比欧拉筛快但比优化版慢。实操心得在绝大多数编程竞赛和日常应用中当N在10^7一千万到10^8一亿量级时优化后的埃氏筛是首选。它实现了速度、内存和代码复杂度的最佳平衡。只有当N极大例如超过10^9并且你对性能有极致要求愿意为可能的内存分块和更复杂的优化付出代价时才需要深入考虑欧拉筛的进一步优化变种。如何选择教学与理解从基础埃氏筛开始理解筛法的思想。竞赛与面试掌握优化埃氏筛和欧拉筛的原理与实现并能解释其区别。通常写优化埃氏筛就足够了。极端性能需求考虑欧拉筛并可能结合分块筛法Segmented Sieve来处理无法一次性装入内存的超大范围。5. 常见问题与排查技巧实录在实际实现和使用筛法时你肯定会遇到一些“坑”。下面是我总结的常见问题及解决方法。5.1 数组越界与溢出这是最常出现的两类运行时错误。问题1内层循环起始点i*i导致整数溢出。// 错误示例 for (int i 2; i * i n; i) { // 当i较大时i*i可能溢出 for (int j i * i; j n; j i) { // j的初始值i*i已溢出行为未定义 // ... } }解决方案将循环变量或乘法结果升级到更宽的类型如long long。for (long long i 2; i * i n; i) { for (long long j i * i; j n; j i) { // ... } } // 或者更高效地在循环外计算上限 int limit sqrt(n); // 或使用 (int)sqrt((double)n) for (int i 2; i limit; i) { // ... }问题2优化筛中prime*prime或下标计算溢出。在优化埃氏筛中prime是int但prime*prime很容易超过int范围。必须使用long long进行计算和比较。long long start static_castlong long(prime) * prime; if (start n) continue; int startIndex start / 2; // 注意start是long long但除法后赋值给int5.2 性能陷阱陷阱1在循环条件中重复计算sqrt(n)。for (int i 2; i sqrt(n); i) { // 每次循环都计算sqrt慢解决在循环前计算一次。int limit static_castint(std::sqrt(n)); for (int i 2; i limit; i) {陷阱2使用vectorint或普通数组存储布尔值。一个bool在C中通常占1字节而一个int占4字节。使用vectorint会浪费4倍内存降低缓存效率。务必使用vectorbool或bitset。陷阱3输出操作耗时。如果你的目的是计算素数个数或进行后续处理在性能测试时避免将大量素数输出到控制台。cout输出是极其缓慢的。可以改为计数或写入文件进行测试。5.3 算法正确性验证如何确保你写的筛法是正确的对于小范围N可以用最笨的试除法进行交叉验证。bool isPrimeTrial(int num) { if (num 2) return false; for (int i 2; i * i num; i) { if (num % i 0) return false; } return true; } void validateSieve(const std::vectorbool isPrime, int n) { for (int i 0; i n; i) { bool sieveResult isPrime[i]; bool trialResult isPrimeTrial(i); if (sieveResult ! trialResult) { std::cerr Mismatch at i : Sieve sieveResult , Trial trialResult std::endl; } } std::cout Validation passed (if no errors above). std::endl; }在开发阶段用这个函数验证你的筛法结果可以快速定位逻辑错误比如下标映射错误、循环条件错误等。5.4 内存与规模限制当N非常大例如10亿时即使使用vectorbool约120MB内存也可能成为问题。这时需要采用分段筛法。 分段筛法的思想是将区间[2, N]分成若干个小段每次只将当前段加载到内存中进行筛除。它需要预先筛出√N以内的素数称为“基础素数”然后用这些素数去筛每一个小段。其核心代码结构如下用普通筛法找出sqrt(N)以内的所有素数存储在basePrimes中。将[2, N]划分为长度为SEG_SIZE的段如[2, SEG_SIZE],[SEG_SIZE1, 2*SEG_SIZE], …。对于每一段[low, high]创建一个布尔数组segment大小为high-low1初始为true。对于每个基础素数p找到段内第一个能被p整除的数start max(p*p, ((low p - 1) / p) * p)。从start开始以p为步长将segment[start-low],segment[start-lowp], … 标记为false。处理完所有基础素数后segment中为true的位置对应的数字lowindex就是该段内的素数。分段筛法将内存需求从O(N)降到了O(√N SEG_SIZE)是处理海量数据的关键技术。
