C++质数筛法详解：从埃氏筛到线性筛的算法优化与实践

1. 项目概述从一道题到一类算法最近在洛谷上刷题又碰到了老朋友——质数判断。P5736这道题要求我们输入一串整数然后输出其中所有的质数。乍一看这题简单得不行不就是写个isPrime函数然后遍历判断吗很多新手朋友可能随手就写了个从2到sqrt(n)的循环判断。但如果你真这么做了当题目要求你从海量数据比如上百万个数中筛选质数或者需要你快速生成一个超大范围内的所有质数时这种朴素的暴力判断法就会立刻让你体会到什么叫“超时”的绝望。这道题真正的价值不在于教会你判断一个数是不是质数而在于它逼着你思考如何高效地、批量地处理质数问题。这就是“质数筛法”登场的时刻。它不是一个函数而是一整套算法思想专门用来解决“找出1到N之间所有质数”这类经典问题。在算法竞赛和实际工程中比如密码学、哈希函数设计筛法的效率直接决定了程序的性能天花板。今天我就结合这道洛谷P5736来彻底拆解一下如何在C中实现高效的质数筛选与过滤算法让你不仅会做题更能理解背后的优化逻辑以后遇到类似问题都能举一反三。2. 核心需求解析与算法选型P5736的题目要求很明确给定n个整数输出其中所有的质数。但我们要把问题抽象化、一般化。其核心需求可以拆解为两点批量判断需要对一组输入数据进行质数判定。高效过滤当数据量巨大或数值范围很广时判断速度必须快。基于此我们有几种算法路径可以选择2.1 路径一朴素试除法对每个输入的数字num用for (int i2; i*inum; i)循环判断是否能被i整除。这是最直观的方法。优点实现简单内存占用小O(1)适用于单个或少量数字的判断。缺点时间复杂度高。判断一个数n需要O(√n)的时间。如果要对m个数进行判断最坏情况总复杂度为O(m * √(max_num))。当m和max_num都很大时效率极低。2.2 路径二预处理筛法这是解决本题乃至一类问题的关键思路。我们注意到题目虽然给的是零散的一串数但这些数总有一个最大值max_val。我们可以先预处理利用筛法快速找出从1到max_val之间所有的质数并存储在一个查询表比如布尔数组里。然后对于输入的每一个数我们只需要O(1)的时间去查表就能知道它是不是质数。优点查询速度极快O(1)特别适合需要多次、批量查询的场景。预处理的时间复杂度取决于筛法的效率。缺点需要额外的O(max_val)的内存空间来存储筛表。如果max_val非常大比如超过10^8内存可能成为瓶颈。2.3 路径三混合策略对于输入数据范围max_val极大但数据量m相对较小的极端情况可以先对输入数据排序然后用线性筛只生成覆盖这些数据所需范围的质数表再进行二分查找。这属于更高级的优化在P5736的语境下通常用不到。结论对于P5736以及大多数需要处理“一组数中找质数”的问题预处理筛法是综合性能最优的选择。接下来的重点就是实现一个高效的筛法。3. 质数筛法原理与C实现细节质数筛法的核心思想是“标记排除”而不是“计算判断”。我们从一个初始假设所有数都是质数出发通过已知质数的倍数反向标记出合数剩下的就是质数。下面介绍三种主流的筛法及其C实现。3.1 埃拉托斯特尼筛法这是最古老、最著名的筛法简称埃氏筛。算法步骤创建一个大小为n1的布尔数组isPrime[]初始化所有元素为true假设都是质数。isPrime[0] isPrime[1] false。从p 2开始遍历到sqrt(n)因为一个合数n必定有一个因子小于等于sqrt(n)。如果isPrime[p]为true那么p是一个质数。然后将p的所有倍数从p*p开始到n为止标记为false即合数。为什么从p*p开始因为比p*p小的p的倍数如2p,3p, ...,(p-1)p已经被更小的质数2, 3, ..., p-1标记过了。遍历结束后数组中仍为true的下标就是质数。C实现代码#include vector #include cmath using namespace std; vectorbool sieveOfEratosthenes(int n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; int sqrt_n sqrt(n); for (int p 2; p sqrt_n; p) { if (isPrime[p]) { // 从 p*p 开始标记步长为 p for (int multiple p * p; multiple n; multiple p) { isPrime[multiple] false; } } } return isPrime; }复杂度分析时间复杂度O(n log log n)。这个复杂度已经非常接近线性对于n10^6效率很高。空间复杂度O(n)用于存储布尔数组。注意埃氏筛有一个小缺陷就是有些合数会被它的多个质因子重复标记例如6会被2和3各标记一次。虽然不影响正确性但存在微小的效率损失。这也是线性筛优化的出发点。3.2 欧拉筛欧拉筛也叫线性筛它的目标是让每个合数只被标记一次从而将时间复杂度严格降到O(n)。算法核心维护一个质数表primes和一个标记数组isPrime。遍历从2到n的每个整数i。如果isPrime[i]为true则将i加入质数表primes。无论i是不是质数都遍历当前的质数表primes令当前质数为p。标记isPrime[i * p] false。关键点当i % p 0时跳出内层循环。这是因为如果i能被p整除那么i * p这个合数的最小质因子就是p。对于后续更大的质数pi * p这个合数应该由(i / p * p) * p来标记才能保证其被最小质因子筛掉避免重复。C实现代码vectorbool linearSieve(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 p : primes) { long long multiple 1LL * i * p; // 防止溢出 if (multiple n) break; isPrime[multiple] false; // 核心保证每个合数只被其最小质因子筛掉 if (i % p 0) { break; } } } // 函数返回isPrime数组primes数组如果需要也可以返回或另存 return isPrime; }复杂度分析时间复杂度O(n)。每个合数只被标记一次每个数也只被内层循环访问有限次严格线性。空间复杂度O(n)用于存储布尔数组和质数列表。实操心得线性筛的代码比埃氏筛稍复杂理解其“最小质因子”的保证机制是关键。在竞赛中如果n在10^7量级埃氏筛和线性筛的时间差距可能不明显但到了10^8或更大线性筛的优势就体现出来了。另外线性筛的primes数组本身就是一个有序的质数列表有时可以直接利用。3.3 针对P5736的优化实现对于P5736我们采用“预处理筛法查表”的策略。步骤清晰读入所有数字并记录最大值max_val。使用筛法埃氏筛或线性筛生成1到max_val的质数布尔表。遍历输入的数字查表输出质数。完整AC代码示例使用埃氏筛#include iostream #include vector #include cmath using namespace std; int main() { int n; cin n; vectorint nums(n); int max_val 0; // 读入数据并找到最大值 for (int i 0; i n; i) { cin nums[i]; if (nums[i] max_val) { max_val nums[i]; } } // 边界情况处理如果最大值小于2则没有质数 if (max_val 2) { // 根据题目要求输出可能什么都不输出或换行 return 0; } // 步骤1使用埃氏筛生成质数表 vectorbool isPrime(max_val 1, true); isPrime[0] isPrime[1] false; // 0和1不是质数 int sqrt_max sqrt(max_val); for (int p 2; p sqrt_max; p) { if (isPrime[p]) { for (int multiple p * p; multiple max_val; multiple p) { isPrime[multiple] false; } } } // 步骤2过滤并输出质数 for (int num : nums) { // 注意查表前要确保下标有效。因为筛表只生成到max_val。 // 理论上nums里的数都不会超过max_val但防御性编程可以加判断if(num max_val isPrime[num]) // 本题中num一定在范围内所以直接判断。 if (isPrime[num]) { cout num ; } } // 注意输出格式有时题目要求空格分隔末尾无空格这里简单处理。可根据具体调整。 // cout endl; return 0; }4. 性能对比与进阶优化探讨了解基础实现后我们深入看看不同筛法在性能上的细微差别以及一些极端情况下的优化手段。4.1 埃氏筛 vs. 线性筛实测数据说话为了有个直观感受我写了个简单的测试程序在相同的环境下开启-O2优化计算筛选1e7一千万以内的质数所需时间。筛法类型时间复杂度 (理论)实测时间 (近似)内存占用代码复杂度埃拉托斯特尼筛O(n log log n)~120 msO(n)简单欧拉筛 (线性筛)O(n)~180 msO(n)中等看到结果你可能会疑惑为什么理论更优的线性筛反而慢了这涉及到计算机的实际运行效率。埃氏筛的内层循环for (multiple p*p; multiple n; multiple p)非常简单CPU的流水线和缓存预取机制可以很好地处理这种连续的内存访问。而线性筛的内层循环需要遍历一个动态增长的primes数组并且有一个条件判断if (i % p 0) break这些操作引入了更多的分支预测和随机内存访问在数据规模不是特别巨大时其常数因子可能更大。结论在n 10^7的范围内埃氏筛往往更快且代码更简单是竞赛和一般应用的首选。当n超过10^8线性筛避免重复标记的优势才会逐渐抵消其常数开销体现出理论复杂度的优势。对于P5736数据范围通常不会超过10^6埃氏筛完全够用且更优。4.2 内存优化位筛当n非常大比如10^8一个bool数组需要10^8字节 ≈ 100 MB内存。bool在C中通常占用1字节。我们可以用位运算来压缩内存用一个bitset或者自己操作unsigned int的每一位来表示一个数的状态这样内存可以缩减到原来的1/8约12.5 MB。使用std::bitset的埃氏筛示例#include bitset #include cmath using namespace std; const int MAX_N 100000000; // 1e8 bitsetMAX_N 1 isPrime; // 默认所有位为0我们让0表示质数1表示合数或反过来 void bitSieve(int n) { isPrime.set(); // 设置所有位为1假设都是质数 isPrime[0] isPrime[1] 0; int sqrt_n sqrt(n); for (int p 2; p sqrt_n; p) { if (isPrime[p]) { for (long long multiple 1LL * p * p; multiple n; multiple p) { isPrime[multiple] 0; } } } } // 查询时if (isPrime[num]) { ... }bitset在访问时会有少许性能开销但换来了巨大的内存节省使得在内存限制严格的场景下处理更大数据成为可能。4.3 分段筛如果要筛选的n大到无法一次性装入内存例如10^9以上就需要用到分段筛或称区间筛。其思想是先筛出sqrt(R)以内的所有质数这个范围小可以全内存操作然后用这些质数去标记大区间[L, R]内的合数。每次只处理区间的一小段使其能放入内存。算法简述用普通筛法生成[2, sqrt(R)]内的所有质数。将大区间[L, R]分成若干个长度为len的小段len约等于内存能容纳的大小。对每一小段[low, high]创建一个布尔数组segment[0...high-low]初始认为段内所有数都是质数。用第一步得到的所有质数p去标记当前段内的合数。找到第一个大于等于low的p的倍数start max(p*p, ((low p - 1) / p) * p)然后从start开始以p为步长标记合数。处理完当前段后段内未被标记的就是质数输出或保存。然后处理下一段。分段筛是处理超大规模质数筛选问题的终极武器在分布式计算和密码学研究中都有应用。5. 洛谷P5736的完整解题与调试实录让我们回到题目本身把上面的知识串联起来完成一次从读题到AC的完整过程并记录下常见的坑点。5.1 题目要求再确认P5736的典型输入输出格式输入 10 2 3 4 5 6 7 8 9 10 11 输出 2 3 5 7 11我们需要输出输入序列中的所有质数顺序与原输入一致并且通常以空格分隔。这里有一个易错点如果输入序列中有负数、0或1它们不是质数应该被过滤掉。我们的筛表从0开始已经正确处理了。5.2 代码实现与逐行解析这里给出一个使用埃氏筛的、鲁棒性更强的版本包含了详细的注释。#include iostream #include vector #include cmath using namespace std; int main() { ios::sync_with_stdio(false); // 关闭C和C的输入输出同步加速 cin.tie(nullptr); // 解绑cin和cout的关联进一步加速 int n; cin n; vectorint a(n); int max_num 0; // 读取并找出最大值同时可以处理非正数 for (int i 0; i n; i) { cin a[i]; // 只对大于1的数感兴趣因为只有它们才可能是质数 if (a[i] max_num) { max_num a[i]; } } // 特殊情况如果最大值小于2则没有质数直接结束 if (max_num 2) { // 根据题目要求可能不需要输出任何东西或者输出一个空行 return 0; } // 步骤1埃氏筛预处理 // 使用vectorbool它可能被编译器特殊优化为位存储节省空间 vectorbool is_prime(max_num 1, true); is_prime[0] is_prime[1] false; // 0和1不是质数 // 只需筛到sqrt(max_num)即可 int sqrt_max static_castint(sqrt(max_num)); for (int i 2; i sqrt_max; i) { if (is_prime[i]) { // 从i*i开始标记避免重复标记 // 注意i*i可能溢出int所以用long long for (long long j (long long)i * i; j max_num; j i) { is_prime[j] false; } } } // 步骤2过滤输出 // 使用一个标志位控制空格输出实现末尾无多余空格 bool first_output true; for (int num : a) { // 关键查表前必须判断下标是否有效 // 因为输入中可能有小于等于1的数它们不在质数表的有效判断范围内但我们已经初始化了 // 更严谨的判断num 0 num max_num // 由于我们筛表大小为max_num1且num是输入的数理论上num max_num恒成立。 // 但num可能为负数题目通常保证正整数这里防御性判断一下。 if (num 1 is_prime[num]) { // num1 确保了只判断可能为质数的数 if (!first_output) { cout ; } cout num; first_output false; } } // 如果至少输出了一个数最后换行。如果没有任何质数就不换行视题目要求而定通常无影响 if (!first_output) { cout endl; } return 0; }5.3 常见错误与排查技巧在实现和调试过程中以下几个坑几乎每个初学者都会踩数组越界这是最经典的错误。vectorbool is_prime(max_num 1)有效下标是[0, max_num]。在查表is_prime[num]时必须确保num在这个范围内。如果输入数据有大于max_num的数逻辑上不可能因为max_num就是它们的最大值或者有负数就会越界。防御性编程在查表前加判断if (num 0 num max_num)。整数溢出在埃氏筛的内层循环for (int j i * i; ...)中当i较大时例如超过46340因为46340*46340 2^31i * i会超出int的表示范围导致溢出变成负数循环条件j max_num可能永远成立或错误导致程序崩溃或死循环。必须使用long longfor (long long j (long long)i * i; ...)。1和0的处理0和1不是质数。必须在初始化筛表后立刻将is_prime[0]和is_prime[1]设为false。很多同学忘记处理1导致输出错误。输出格式题目要求空格分隔但末尾不能有空格。上面代码使用了first_output标志位来控制。也可以先收集结果到vector最后再统一输出。性能陷阱筛到n而不是sqrt(n)最外层的for循环如果写成for (int i2; imax_num; i)时间复杂度就退化到了O(n^2)量级必然超时。重复创建筛表如果对每组输入数据都重新创建和筛选一次在有多组测试数据时会非常慢。正确的做法是如果多组数据的最大值max_num不变或只增不减可以只筛一次重复利用筛表。输入加速当输入数据量很大时比如n10^5使用cin/cout可能会比较慢。可以采用ios::sync_with_stdio(false); cin.tie(nullptr);来禁用同步和解绑能显著提升速度。在竞赛中这是常用技巧。6. 算法扩展与应用场景掌握了质数筛你就解锁了解决一系列问题的能力。它不仅仅是解一道题。6.1 相关洛谷题目推荐你可以用筛法轻松解决以下问题P3383 【模板】线性筛素数纯粹的线性筛模板题。P1217 [USACO1.5]回文质数 Prime Palindromes需要生成质数并判断回文筛法生成质数表是第一步。P1304 哥德巴赫猜想给定一个偶数将其分解为两个质数之和。需要快速查询一个数是否为质数筛法预处理质数表是标准做法。P1835 素数密度给定区间[L, R]求区间内质数个数。这是分段筛的经典应用题。6.2 实际工程中的应用质数筛的思想和变种在计算机科学中广泛应用密码学RSA等公钥加密算法依赖于大质数的生成与判断。高效的质数测试算法如Miller-Rabin是核心而筛法常被用于预生成小质数表辅助更快的质数测试。哈希函数设计一些哈希表的大小会选择质数以减少哈希冲突。筛法可以快速生成一个范围内的质数供选择。数论计算在解决涉及质因数分解、欧拉函数、莫比乌斯函数等问题时经常需要快速获取一个范围内所有数的最小质因子。线性筛在筛质数的同时可以很容易地记录每个数的最小质因子功能非常强大。// 线性筛的同时记录最小质因子 vectorint min_prime_factor(n1, 0); vectorint primes; for (int i2; in; i) { if (min_prime_factor[i] 0) { // i是质数 min_prime_factor[i] i; primes.push_back(i); } for (int p : primes) { if (p min_prime_factor[i] || i * p n) break; min_prime_factor[i * p] p; } }算法竞赛是基础数论知识的必备组成部分是解决更复杂数论问题的基石。从一道简单的洛谷练习题出发我们深入探讨了质数筛法的原理、多种实现、性能差异、优化技巧以及实际应用。记住埃氏筛O(n log log n)在大多数情况下n ≤ 10^7是简单高效的首选当需要严格线性时间或同时求取最小质因子等额外信息时线性筛O(n)是更优解面对内存限制或超大范围位筛和分段筛则是必要的武器。理解算法背后的“为什么”比记住代码本身更重要。希望这篇长文能帮你把“质数筛”这个知识点彻底吃透下次遇到相关问题无论是竞赛还是开发都能游刃有余。