埃氏筛在n ≤ 10⁶且单次调用时完全够用，代码简洁、逻辑清晰、调试友好，适用于教学、本地预处理或leetcode小数据量题；超10⁷时性能明显下降。
埃氏筛 sieve_eratosthenes 什么时候够用？
当 n ≤ 10⁶ 且你只调用一次、不频繁重算时，sieve_eratosthenes 完全够用。它代码短、逻辑直白、调试友好，适合教学、本地预处理或 LeetCode 小数据量题（如 n = 5 × 10⁵）。
常见误判点：
- 外层循环写成
i 而不是 <code>i * i → 时间直接退化到 <code>O(n²) - 内层从
j = 2 * i开始 → 大量重复标记（比如12被2和3各筛一次） - 用
int j = i * i导致溢出（i > 46340时i*i溢出）→ 必须转long long或加提前截断
欧拉筛 linear_sieve 真正发挥优势的场景
只有当你需要在运行时动态扩展素数表、或 n ≥ 5 × 10⁶ 且对单次耗时敏感（比如在线 OJ 卡 1s 时限），才值得上 linear_sieve。它的核心价值不是“更快”，而是“每个合数只被访问一次”。
关键约束必须满足：
- 内层循环中，
if (i % p == 0) break;缺一不可 —— 少这句就退化成埃氏筛 -
primes容器不能用vector<bool></bool>存，得用vector<int></int>或vector<char></char>，否则取不到值 -
i * p判断上界前必须先转long long，否则i和p都接近10⁴时乘积就溢出
内存与缓存行为差异直接影响实测性能
埃氏筛访问模式是跳跃式：筛 2 时访问下标 4,6,8,...；筛 3 时访问 9,12,15,... —— 这导致 CPU 缓存命中率低，尤其在 n > 10⁷ 时明显变慢。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
欧拉筛是顺序写入：is_composite[i * p] 的 i 递增、p 来自小素数列表，地址局部性好。但多一个 primes 数组，空间占用略高约 π(n) × sizeof(int)（π(10⁷) ≈ 664579）。
所以：若你内存受限（比如嵌入式环境），或只需查少量素数（n ），别硬套线性筛。
别忽略初始化和复用成本
两种筛法都需一次性初始化布尔数组。但很多人忘了：如果你要反复查询不同 n 值下的素数个数（比如多次调用 countPrimes(q)），埃氏筛每次都要重筛；而欧拉筛只要筛到全局最大 N，后续所有 q ≤ N 都可 O(1) 查前缀和。
此时真正该写的是：
- 一次
linear_sieve(MAX_N) - 配套
vector<int> prefix</int>记录前缀素数个数 - 查询直接
return prefix[q]
这个组合才是工业级用法。单独谈“哪个筛快”没意义——快慢取决于你怎么用，而不是函数名本身。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
