洛谷P5736【深基7.例2】质数筛题面就一句话输入 n 个数把里面的质数挑出来。我刚接触这道题时觉得它简单到不需要动脑直接每个数从2除到√x交上去一路AC。可等我回头翻题解看到埃氏筛、欧拉筛两种写法摆在眼前才明白这道题真正的用心它用一组“数量少但值很大”的数据逼你去想筛表的边界该划在哪里想筛法为什么比逐个试除舒服以及什么时候筛法反而不能硬套。这些想明白了P5736才算真正做完了。这篇内容适合三种人刚刷完分支循环、第一次接触质数筛的新手会背埃氏筛但没认真推导过欧拉筛的进阶选手以及想认真吃透一道基础题的严谨型刷题人。我会把题目数据拆开讲再把两种筛法的原理、代码、坑点一条龙铺开最后聊聊筛法还能往哪些方向延伸。1. 题目拆解P5736到底在考什么1.1 数据范围的设计意图先看数据范围n≤100每个数不超过10^9。这个组合非常有意思。如果n很大而ai很小比如n10^5、ai≤10^6那题目指向很明显直接把1到10^6的质数表筛出来再用O(1)判断每个ai。如果n很小而ai也很小比如ai≤100那暴力试除就完事了根本不用学筛法。偏偏它给的是n100、ai≤10^9卡在中间。如果暴力判断每个数单个数要试除到√(10^9)≈31623100个数最多做316万次取模程序眨眼就跑完了所以单纯为了AC暴力确实能过。但问题来了题目名字叫“质数筛”考察点注定是筛法。你见过哪道叫“质数筛”的题让你一个一个试除的所以这道题的正确姿态是先筛出一张足够大的质数表再用这张表去判定输入的每个数。这里就引出一个关键判断需要筛到多大因为ai最大是10^9合数x一定有一个不超过√x的质因子√(10^9)≈31623。所以只要筛出31623以内的质数就能覆盖所有10^9以内合数的最小质因子范围。这个“筛表上限跟着判定需求走”的思想是这题真正想教的东西也是后面很多数论题的共同起点。1.2 暴力试除能AC但你真的会筛法吗我把三条路线的复杂度拉一张表看完你就明白出题人为什么这么设计数据解法预处理复杂度判断每个数在P5736上的表现适用场景纯试除法无O(√ai)约316万次取模能过n很小或数很小筛sqrt(1e9)内质数试除O(LIM log log LIM)约3400次试除约34万次取模毫秒级ai达到1e9量级把1到1e9全部筛出来O(1e9 log log 1e9)O(1)查表内存接近1GB直接寄ai≤1e6且内存允许先解释一下3400这个数字31623以内一共有约3401个质数π(31623)≈3401所以用质数表试除一个10^9以内的数最坏情况就是从头试到p*px为止最多3400次取模。100个数就是34万次比暴力的316万次少了一个数量级。再看第三种方案如果真的开一个bool数组标记1到10^9的合数bool在C里是1字节光数组就要1GBOJ上根本开不出来。即使用bitset压缩成1bit也要125MB依然不安全。所以这道题不能“无脑筛到最大值”必须筛到根号级别再用质数表去试除。这个“筛表上限折中”的设计才是筛法是否适用的核心分界线。2. 埃氏筛简单直观的合数标记法2.1 核心思想质数留名合数划掉埃氏筛全称是“埃拉托斯特尼筛法”思路朴素到一句话就能说清一个质数的倍数一定是合数。从2开始遍历如果当前数字i没被标记为合数那它就是质数然后把i的所有倍数标记成合数。一直做到上限剩下的没被标记的数全是质数。这里有一个很关键的优化标记倍数时不需要从2i开始直接从i*i开始就够了。为什么因为2i、3i、(i-1)i这些数都已经被更小的质因数筛过了。比如i7时2×714早被2筛过3×721早被3筛过5×735早被5筛过所以直接从7×749开始标记。这个优化能省掉大量重复工作尤其对较大的质数。这个思想用生活类比来说就像开班会点名每报到一个人就把所有和他同宿舍的人都划掉剩下没被划掉的就是独立宿舍。虽然划人的时候可能有人被划了好几次但整体上效率比挨个问“你是不是独立宿舍”高得多。2.2 代码实现与两个关键优化点埃氏筛的代码非常短const int LIM 31623; vectorint primes; bool isComp[LIM 1]; void eratosthenesSieve() { for (int i 2; i LIM; i) { if (!isComp[i]) { primes.push_back(i); for (long long j 1LL * i * i; j LIM; j i) { isComp[j] true; } } } }这段代码里有三个细节值得单独拎出来说。第一1LL * i * i这个写法看起来多余其实是在防int溢出。LIM31623时ii≈10^9还没超过int上限但万一你把LIM改成40000ii就到16亿了还在int范围内改成50000i*i就是25亿直接溢出变成负数后面的循环就可能死循环或者漏筛。养成写1LL * i * i的习惯换数据范围时不会踩坑。第二为什么不在外层循环里把所有数的倍数都筛一遍而是只在if (!isComp[i])成立时筛因为如果i已经被标记为合数说明i有更小的质因子i的所有倍数也必然有这个质因子早就被更小的质数标记过了再筛一遍纯属浪费。第三内层循环从ii开始这一句我前面讲过了。但注意如果ii已经超过LIM内层循环不会执行但i本身依然要加入primes表。也就是说埃氏筛的加入质数表和标记倍数是两件可以分开做的事。3. 欧拉筛每个合数只被筛一次3.1 埃氏筛的冗余在哪里埃氏筛有个小毛病同一个合数会被标记好多次。比如122的倍数会标记它3的倍数也会标记它再比如302、3、5都会标记它。虽然从整体上看埃氏筛的时间复杂度是O(n log log n)已经非常接近线性但标记次数的冗余始终让人不舒服。当筛法规模大到1e7甚至1e8时这个冗余就明显了。欧拉筛也叫线性筛就是冲着“每个合数只被筛一次”去的它能把总复杂度稳定在O(n)。欧拉筛的思路是每个合数只被它的最小质因子筛掉。比如12只让质数2去筛它不让3去筛它30只让2去筛不让3和5去筛。要做到这一点就不能像埃氏筛那样一个质数一路标到底而要在标记过程中随时“刹车”。3.2 线性筛原理与核心break条件看代码const int LIM 31623; vectorint primes; bool isComp[LIM 1]; void linearSieve() { for (int i 2; i LIM; i) { if (!isComp[i]) { primes.push_back(i); } for (int p : primes) { if (1LL * i * p LIM) break; isComp[i * p] true; if (i % p 0) break; } } }外层循环的i从2走到LIM遇到没被标记的就加入primes表。内层循环遍历当前已有的质数表把i*p标记为合数。两个break缺一不可。第一个break很好理解ip超过LIM就没必要标记了而且因为p是从小到大枚举的后面更大的p只会让ip更大直接终止循环。第二个break才是线性筛的灵魂当i % p 0时立即停止。为什么假设p能整除i那么p就是i的最小质因子。此时设i p * k我们来考虑i的下一个质数qq p。iq p * k * q这个数的最小质因子是p不是q。按照“每个合数只被最小质因子筛掉”的原则iq应该由外层走到kq时内层枚举到p来筛掉而不是现在由i和q来筛。所以现在必须break把筛掉iq的机会留给未来。所以“每个合数只被最小质因子筛一次”是怎么保证的对任意合数x设m是x的最小质因子x m * t。当外层循环i走到t时内层枚举p从小到大pm时一定满足i%p0因为m|t于是标记i*px后breakx被m筛掉。而x不会再被其他质因子筛掉因为其他质因子对应的情况都被break拦截了。这个保证是严谨的不是玄学。如果你把if (i % p 0) break;写成continue结果依然正确因为continue会让循环继续枚举更大的p重复标记某些合数复杂度退化。如果你干脆不写这个break那所有质数都会一直乘到上界重复标记的合数数量会回到接近埃氏筛甚至更多线性性质就丢了。4. 两种方案落地这道题4.1 完整解题流程筛表试除判定回到P5736。既然ai最大10^9我们的策略就是先筛出31623以内的质数表然后对每个输入的数x用质数表从小到大试除只要p*p x就停止。判断函数的写法bool isPrime(int x) { if (x 2) return false; for (int p : primes) { if (1LL * p * p x) break; if (x % p 0) return false; } return true; }这里有一个微妙的逻辑如果x本身就是质数比如x99999993710^9以内最大的质数之一试除过程中p*p始终小于x一直到p超过√x才break最后返回true。如果x是合数它必然有一个不超过√x的质因子这个质因子一定在primes表里因为我们筛到了31623≥√x试除到它时就会返回false。还有一种边界情况x本身就在质数表里比如x3162331623不是质数316233×10541但x31607这样接近31623的质数是存在的。这时p枚举到最接近√x的质数后p*px触发了break返回true不需要真的把x本身筛进表里来判断。这种“筛根号范围试除判定”的组合比我之前说的纯暴力快一个数量级又比直接筛到1e9节省了海量内存本质上是在时间、空间、代码复杂度三者之间找到了平衡点。4.2 完整参考代码C把上面几段拼起来就是一份可以直接提交的完整代码#include bits/stdc.h using namespace std; const int LIM 31623; vectorint primes; bool isComp[LIM 1]; void eratosthenesSieve() { for (int i 2; i LIM; i) { if (!isComp[i]) { primes.push_back(i); for (long long j 1LL * i * i; j LIM; j i) { isComp[j] true; } } } } bool isPrime(int x) { if (x 2) return false; for (int p : primes) { if (1LL * p * p x) break; if (x % p 0) return false; } return true; } int main() { eratosthenesSieve(); int n; cin n; vectorint ans; for (int i 0; i n; i) { int x; cin x; if (isPrime(x)) ans.push_back(x); } sort(ans.begin(), ans.end()); for (size_t i 0; i ans.size(); i) { if (i) cout ; cout ans[i]; } cout \n; return 0; }如果你想用欧拉筛只需要把eratosthenesSieve替换成前面的linearSieve即可判断函数和主函数完全不用动。这两种筛法在LIM31623时性能差距可以忽略但代码逻辑都要能写对。4.3 输出排序与重复数值的坑这道题有个隐藏考点题目要求“从小到大输出所有质数”不是按输入顺序。我第一次做的时候直接在读入循环里判断完就输出完全没排序结果WA。后来仔细读题才发现要sort一下。如果你的答案数组用的是vector一句sort(ans.begin(), ans.end())就搞定了但别忘了。还有一个值得讨论的点如果输入里有两个相同的质数比如5出现了两次输出时要输出两个5还是一个5原题面说的是“从小到大输出所有质数”并没有提“去重”所以按竞赛惯例每个数都要输出也就是重复的质数要输两次。除非题面明确写了“不重复输出”或“输出不同的质数”否则不要去重。很多新手在这里凭感觉自作主张去重反而做错了。5. 常见错误与调试经验5.1 数组上限到底开多大最典型的错误是LIM设得太小比如随手写个10000或者sqrt(1000000000)时向下取整成31622。如果LIM31622万一输入的数是31622的平方附近的合数它的质因子在质数表里没有完整覆盖就可能误判。所以稳妥做法是注意LIM取sqrt(所有输入数的上限)1确保向上取整。本题直接写成31623即可写40000甚至100000也完全没问题筛表越大试除次数越多但依然不会超时。我见过有人写1000000筛了一百万的质数表用来判断10^9以内的数答案正确但预处理时间明显变长。筛表不是越大越好够用就行这也是刷题时需要注意的平衡感。5.2 欧拉筛break条件写错的表现如果你在欧拉筛里漏掉了if (i % p 0) break;程序不会WA因为合数依然都被标记了。但它会导致大量重复标记复杂度从O(n)退化为接近O(n log n)。你在LIM31623时根本感觉不到差异一旦拿到LIM1e7的题运行时间可能从0.1秒变成1秒多直接TLE。调试这类问题有个笨办法小范围对比。把LIM改成50分别跑埃氏筛和欧拉筛打印每个合数被标记的次数。如果欧拉筛标记次数不是1说明break位置写错了。我最初学线性筛时就是靠这个办法一步步看懂“最小质因子”机制的。5.3 边界值1和0的处理1既不是质数也不是合数0和负数更不用谈。判断函数开头那句if (x 2) return false;就是专门挡这些边界的。虽然题面保证输入是正整数但自测时我习惯把0和1都测一遍防止自己写的判断逻辑在边界上出问题。另外质数表生成是从2开始的数组isComp[0]和isComp[1]虽然默认false但这两个位置永远不会被访问也不会影响逻辑。如果某个版本的筛法代码从1开始循环就可能出现把0和1当成质数的bug看到这类代码要警惕。我顺手整理了一张常见错误速查表做题时对着排查效率很高错误类型现象根本原因修复方式LIM设太小大合数被误判为质数质因子不在筛表内LIM取√上限1int平方溢出死循环或漏筛i*i超过2^31-1用1LLii输出前不排序WA题目要求从小到大收集后sort欧拉筛漏break大量重复标记合数被多个质因子筛补上i%p0时break把1当质数WA边界未处理x2直接返回false重复质数去重WA误解题意按题面要求不去重6. 从P5736延伸出去筛法的真正用武之地6.1 最小质因子预处理与质因数分解埃氏筛和欧拉筛标记合数的时候可以顺手记录每个数的最小质因子。比如在标记isComp[ip]true的同时记录spf[ip]p。在线性筛里由于每个合数只被筛一次记录的p一定是最小质因子。有了spf数组任意数x的质因数分解就变成O(log x)的机械操作反复取spf[x]然后x/spf[x]一边除一边统计。这对做约数个数、约数和、欧拉函数一类数论题帮助极大。P5736只让你判断质数但“筛表时多记一个数组”的习惯值得从这道题开始养成。6.2 线性筛还能顺便求积性函数线性筛的价值不止是筛质数。欧拉函数φ、莫比乌斯函数μ、约数个数d(n)这类积性函数都能在线性筛的过程中同步算出来。以欧拉函数为例如果i与p互质即i%p!0则φ(ip)φ(i)(p-1)如果i%p0则φ(i*p)φ(i)*p这两个递推式刚好和线性筛的循环结构完美匹配。所以你筛完质数表的同时也把1到LIM所有数的欧拉函数算完了。这也是为什么说线性筛是一条“积性函数生产线”而不只是一个质数筛选器。初学时不用急着掌握全部但心里要清楚今天学的if(i%p0)break后面会在无数个写法里再次出现。6.3 什么时候该升级到Miller-Rabin如果有一天你遇到ai上限是10^18的题√上限就是10^9筛表方案直接失效因为内存和时间都不现实。这时候需要换工具Miller-Rabin素性测试。它基于费马小定理和二次探测在选定合适底数的情况下可以在O(k log n)时间内高概率判断一个数是否为质数k一般取3到7个底数就足够。我不建议新手一上来就学Miller-Rabin容易消化不良。更合理的路线是先把P5736这类筛法题吃透理解筛表的边界和复杂度等到真正碰到大素数判定题时再去补数学基础。知道“筛法失效时还有一条路”就已经比很多只背模板的人强了。最后分享一个我个人的小习惯每次写完筛法代码都会拿几个特殊值自测——0、1、2、4、9、一个较大的质数如999999937。这几组数据能一次性暴露数组越界、break条件错误和边界值遗漏三类问题。P5736本身不难但它是一把很好的尺子能把埃氏筛、欧拉筛、筛表上限、边界处理这几个点量得明明白白。把这题彻底吃透后面再遇到区间质数、质因数分解甚至积性函数线性筛你会觉得顺理成章。
洛谷P5736质数筛题解：埃氏筛与欧拉筛原理及C++实现
洛谷P5736【深基7.例2】质数筛题面就一句话输入 n 个数把里面的质数挑出来。我刚接触这道题时觉得它简单到不需要动脑直接每个数从2除到√x交上去一路AC。可等我回头翻题解看到埃氏筛、欧拉筛两种写法摆在眼前才明白这道题真正的用心它用一组“数量少但值很大”的数据逼你去想筛表的边界该划在哪里想筛法为什么比逐个试除舒服以及什么时候筛法反而不能硬套。这些想明白了P5736才算真正做完了。这篇内容适合三种人刚刷完分支循环、第一次接触质数筛的新手会背埃氏筛但没认真推导过欧拉筛的进阶选手以及想认真吃透一道基础题的严谨型刷题人。我会把题目数据拆开讲再把两种筛法的原理、代码、坑点一条龙铺开最后聊聊筛法还能往哪些方向延伸。1. 题目拆解P5736到底在考什么1.1 数据范围的设计意图先看数据范围n≤100每个数不超过10^9。这个组合非常有意思。如果n很大而ai很小比如n10^5、ai≤10^6那题目指向很明显直接把1到10^6的质数表筛出来再用O(1)判断每个ai。如果n很小而ai也很小比如ai≤100那暴力试除就完事了根本不用学筛法。偏偏它给的是n100、ai≤10^9卡在中间。如果暴力判断每个数单个数要试除到√(10^9)≈31623100个数最多做316万次取模程序眨眼就跑完了所以单纯为了AC暴力确实能过。但问题来了题目名字叫“质数筛”考察点注定是筛法。你见过哪道叫“质数筛”的题让你一个一个试除的所以这道题的正确姿态是先筛出一张足够大的质数表再用这张表去判定输入的每个数。这里就引出一个关键判断需要筛到多大因为ai最大是10^9合数x一定有一个不超过√x的质因子√(10^9)≈31623。所以只要筛出31623以内的质数就能覆盖所有10^9以内合数的最小质因子范围。这个“筛表上限跟着判定需求走”的思想是这题真正想教的东西也是后面很多数论题的共同起点。1.2 暴力试除能AC但你真的会筛法吗我把三条路线的复杂度拉一张表看完你就明白出题人为什么这么设计数据解法预处理复杂度判断每个数在P5736上的表现适用场景纯试除法无O(√ai)约316万次取模能过n很小或数很小筛sqrt(1e9)内质数试除O(LIM log log LIM)约3400次试除约34万次取模毫秒级ai达到1e9量级把1到1e9全部筛出来O(1e9 log log 1e9)O(1)查表内存接近1GB直接寄ai≤1e6且内存允许先解释一下3400这个数字31623以内一共有约3401个质数π(31623)≈3401所以用质数表试除一个10^9以内的数最坏情况就是从头试到p*px为止最多3400次取模。100个数就是34万次比暴力的316万次少了一个数量级。再看第三种方案如果真的开一个bool数组标记1到10^9的合数bool在C里是1字节光数组就要1GBOJ上根本开不出来。即使用bitset压缩成1bit也要125MB依然不安全。所以这道题不能“无脑筛到最大值”必须筛到根号级别再用质数表去试除。这个“筛表上限折中”的设计才是筛法是否适用的核心分界线。2. 埃氏筛简单直观的合数标记法2.1 核心思想质数留名合数划掉埃氏筛全称是“埃拉托斯特尼筛法”思路朴素到一句话就能说清一个质数的倍数一定是合数。从2开始遍历如果当前数字i没被标记为合数那它就是质数然后把i的所有倍数标记成合数。一直做到上限剩下的没被标记的数全是质数。这里有一个很关键的优化标记倍数时不需要从2i开始直接从i*i开始就够了。为什么因为2i、3i、(i-1)i这些数都已经被更小的质因数筛过了。比如i7时2×714早被2筛过3×721早被3筛过5×735早被5筛过所以直接从7×749开始标记。这个优化能省掉大量重复工作尤其对较大的质数。这个思想用生活类比来说就像开班会点名每报到一个人就把所有和他同宿舍的人都划掉剩下没被划掉的就是独立宿舍。虽然划人的时候可能有人被划了好几次但整体上效率比挨个问“你是不是独立宿舍”高得多。2.2 代码实现与两个关键优化点埃氏筛的代码非常短const int LIM 31623; vectorint primes; bool isComp[LIM 1]; void eratosthenesSieve() { for (int i 2; i LIM; i) { if (!isComp[i]) { primes.push_back(i); for (long long j 1LL * i * i; j LIM; j i) { isComp[j] true; } } } }这段代码里有三个细节值得单独拎出来说。第一1LL * i * i这个写法看起来多余其实是在防int溢出。LIM31623时ii≈10^9还没超过int上限但万一你把LIM改成40000ii就到16亿了还在int范围内改成50000i*i就是25亿直接溢出变成负数后面的循环就可能死循环或者漏筛。养成写1LL * i * i的习惯换数据范围时不会踩坑。第二为什么不在外层循环里把所有数的倍数都筛一遍而是只在if (!isComp[i])成立时筛因为如果i已经被标记为合数说明i有更小的质因子i的所有倍数也必然有这个质因子早就被更小的质数标记过了再筛一遍纯属浪费。第三内层循环从ii开始这一句我前面讲过了。但注意如果ii已经超过LIM内层循环不会执行但i本身依然要加入primes表。也就是说埃氏筛的加入质数表和标记倍数是两件可以分开做的事。3. 欧拉筛每个合数只被筛一次3.1 埃氏筛的冗余在哪里埃氏筛有个小毛病同一个合数会被标记好多次。比如122的倍数会标记它3的倍数也会标记它再比如302、3、5都会标记它。虽然从整体上看埃氏筛的时间复杂度是O(n log log n)已经非常接近线性但标记次数的冗余始终让人不舒服。当筛法规模大到1e7甚至1e8时这个冗余就明显了。欧拉筛也叫线性筛就是冲着“每个合数只被筛一次”去的它能把总复杂度稳定在O(n)。欧拉筛的思路是每个合数只被它的最小质因子筛掉。比如12只让质数2去筛它不让3去筛它30只让2去筛不让3和5去筛。要做到这一点就不能像埃氏筛那样一个质数一路标到底而要在标记过程中随时“刹车”。3.2 线性筛原理与核心break条件看代码const int LIM 31623; vectorint primes; bool isComp[LIM 1]; void linearSieve() { for (int i 2; i LIM; i) { if (!isComp[i]) { primes.push_back(i); } for (int p : primes) { if (1LL * i * p LIM) break; isComp[i * p] true; if (i % p 0) break; } } }外层循环的i从2走到LIM遇到没被标记的就加入primes表。内层循环遍历当前已有的质数表把i*p标记为合数。两个break缺一不可。第一个break很好理解ip超过LIM就没必要标记了而且因为p是从小到大枚举的后面更大的p只会让ip更大直接终止循环。第二个break才是线性筛的灵魂当i % p 0时立即停止。为什么假设p能整除i那么p就是i的最小质因子。此时设i p * k我们来考虑i的下一个质数qq p。iq p * k * q这个数的最小质因子是p不是q。按照“每个合数只被最小质因子筛掉”的原则iq应该由外层走到kq时内层枚举到p来筛掉而不是现在由i和q来筛。所以现在必须break把筛掉iq的机会留给未来。所以“每个合数只被最小质因子筛一次”是怎么保证的对任意合数x设m是x的最小质因子x m * t。当外层循环i走到t时内层枚举p从小到大pm时一定满足i%p0因为m|t于是标记i*px后breakx被m筛掉。而x不会再被其他质因子筛掉因为其他质因子对应的情况都被break拦截了。这个保证是严谨的不是玄学。如果你把if (i % p 0) break;写成continue结果依然正确因为continue会让循环继续枚举更大的p重复标记某些合数复杂度退化。如果你干脆不写这个break那所有质数都会一直乘到上界重复标记的合数数量会回到接近埃氏筛甚至更多线性性质就丢了。4. 两种方案落地这道题4.1 完整解题流程筛表试除判定回到P5736。既然ai最大10^9我们的策略就是先筛出31623以内的质数表然后对每个输入的数x用质数表从小到大试除只要p*p x就停止。判断函数的写法bool isPrime(int x) { if (x 2) return false; for (int p : primes) { if (1LL * p * p x) break; if (x % p 0) return false; } return true; }这里有一个微妙的逻辑如果x本身就是质数比如x99999993710^9以内最大的质数之一试除过程中p*p始终小于x一直到p超过√x才break最后返回true。如果x是合数它必然有一个不超过√x的质因子这个质因子一定在primes表里因为我们筛到了31623≥√x试除到它时就会返回false。还有一种边界情况x本身就在质数表里比如x3162331623不是质数316233×10541但x31607这样接近31623的质数是存在的。这时p枚举到最接近√x的质数后p*px触发了break返回true不需要真的把x本身筛进表里来判断。这种“筛根号范围试除判定”的组合比我之前说的纯暴力快一个数量级又比直接筛到1e9节省了海量内存本质上是在时间、空间、代码复杂度三者之间找到了平衡点。4.2 完整参考代码C把上面几段拼起来就是一份可以直接提交的完整代码#include bits/stdc.h using namespace std; const int LIM 31623; vectorint primes; bool isComp[LIM 1]; void eratosthenesSieve() { for (int i 2; i LIM; i) { if (!isComp[i]) { primes.push_back(i); for (long long j 1LL * i * i; j LIM; j i) { isComp[j] true; } } } } bool isPrime(int x) { if (x 2) return false; for (int p : primes) { if (1LL * p * p x) break; if (x % p 0) return false; } return true; } int main() { eratosthenesSieve(); int n; cin n; vectorint ans; for (int i 0; i n; i) { int x; cin x; if (isPrime(x)) ans.push_back(x); } sort(ans.begin(), ans.end()); for (size_t i 0; i ans.size(); i) { if (i) cout ; cout ans[i]; } cout \n; return 0; }如果你想用欧拉筛只需要把eratosthenesSieve替换成前面的linearSieve即可判断函数和主函数完全不用动。这两种筛法在LIM31623时性能差距可以忽略但代码逻辑都要能写对。4.3 输出排序与重复数值的坑这道题有个隐藏考点题目要求“从小到大输出所有质数”不是按输入顺序。我第一次做的时候直接在读入循环里判断完就输出完全没排序结果WA。后来仔细读题才发现要sort一下。如果你的答案数组用的是vector一句sort(ans.begin(), ans.end())就搞定了但别忘了。还有一个值得讨论的点如果输入里有两个相同的质数比如5出现了两次输出时要输出两个5还是一个5原题面说的是“从小到大输出所有质数”并没有提“去重”所以按竞赛惯例每个数都要输出也就是重复的质数要输两次。除非题面明确写了“不重复输出”或“输出不同的质数”否则不要去重。很多新手在这里凭感觉自作主张去重反而做错了。5. 常见错误与调试经验5.1 数组上限到底开多大最典型的错误是LIM设得太小比如随手写个10000或者sqrt(1000000000)时向下取整成31622。如果LIM31622万一输入的数是31622的平方附近的合数它的质因子在质数表里没有完整覆盖就可能误判。所以稳妥做法是注意LIM取sqrt(所有输入数的上限)1确保向上取整。本题直接写成31623即可写40000甚至100000也完全没问题筛表越大试除次数越多但依然不会超时。我见过有人写1000000筛了一百万的质数表用来判断10^9以内的数答案正确但预处理时间明显变长。筛表不是越大越好够用就行这也是刷题时需要注意的平衡感。5.2 欧拉筛break条件写错的表现如果你在欧拉筛里漏掉了if (i % p 0) break;程序不会WA因为合数依然都被标记了。但它会导致大量重复标记复杂度从O(n)退化为接近O(n log n)。你在LIM31623时根本感觉不到差异一旦拿到LIM1e7的题运行时间可能从0.1秒变成1秒多直接TLE。调试这类问题有个笨办法小范围对比。把LIM改成50分别跑埃氏筛和欧拉筛打印每个合数被标记的次数。如果欧拉筛标记次数不是1说明break位置写错了。我最初学线性筛时就是靠这个办法一步步看懂“最小质因子”机制的。5.3 边界值1和0的处理1既不是质数也不是合数0和负数更不用谈。判断函数开头那句if (x 2) return false;就是专门挡这些边界的。虽然题面保证输入是正整数但自测时我习惯把0和1都测一遍防止自己写的判断逻辑在边界上出问题。另外质数表生成是从2开始的数组isComp[0]和isComp[1]虽然默认false但这两个位置永远不会被访问也不会影响逻辑。如果某个版本的筛法代码从1开始循环就可能出现把0和1当成质数的bug看到这类代码要警惕。我顺手整理了一张常见错误速查表做题时对着排查效率很高错误类型现象根本原因修复方式LIM设太小大合数被误判为质数质因子不在筛表内LIM取√上限1int平方溢出死循环或漏筛i*i超过2^31-1用1LLii输出前不排序WA题目要求从小到大收集后sort欧拉筛漏break大量重复标记合数被多个质因子筛补上i%p0时break把1当质数WA边界未处理x2直接返回false重复质数去重WA误解题意按题面要求不去重6. 从P5736延伸出去筛法的真正用武之地6.1 最小质因子预处理与质因数分解埃氏筛和欧拉筛标记合数的时候可以顺手记录每个数的最小质因子。比如在标记isComp[ip]true的同时记录spf[ip]p。在线性筛里由于每个合数只被筛一次记录的p一定是最小质因子。有了spf数组任意数x的质因数分解就变成O(log x)的机械操作反复取spf[x]然后x/spf[x]一边除一边统计。这对做约数个数、约数和、欧拉函数一类数论题帮助极大。P5736只让你判断质数但“筛表时多记一个数组”的习惯值得从这道题开始养成。6.2 线性筛还能顺便求积性函数线性筛的价值不止是筛质数。欧拉函数φ、莫比乌斯函数μ、约数个数d(n)这类积性函数都能在线性筛的过程中同步算出来。以欧拉函数为例如果i与p互质即i%p!0则φ(ip)φ(i)(p-1)如果i%p0则φ(i*p)φ(i)*p这两个递推式刚好和线性筛的循环结构完美匹配。所以你筛完质数表的同时也把1到LIM所有数的欧拉函数算完了。这也是为什么说线性筛是一条“积性函数生产线”而不只是一个质数筛选器。初学时不用急着掌握全部但心里要清楚今天学的if(i%p0)break后面会在无数个写法里再次出现。6.3 什么时候该升级到Miller-Rabin如果有一天你遇到ai上限是10^18的题√上限就是10^9筛表方案直接失效因为内存和时间都不现实。这时候需要换工具Miller-Rabin素性测试。它基于费马小定理和二次探测在选定合适底数的情况下可以在O(k log n)时间内高概率判断一个数是否为质数k一般取3到7个底数就足够。我不建议新手一上来就学Miller-Rabin容易消化不良。更合理的路线是先把P5736这类筛法题吃透理解筛表的边界和复杂度等到真正碰到大素数判定题时再去补数学基础。知道“筛法失效时还有一条路”就已经比很多只背模板的人强了。最后分享一个我个人的小习惯每次写完筛法代码都会拿几个特殊值自测——0、1、2、4、9、一个较大的质数如999999937。这几组数据能一次性暴露数组越界、break条件错误和边界值遗漏三类问题。P5736本身不难但它是一把很好的尺子能把埃氏筛、欧拉筛、筛表上限、边界处理这几个点量得明明白白。把这题彻底吃透后面再遇到区间质数、质因数分解甚至积性函数线性筛你会觉得顺理成章。
