埃氏筛不超时的关键是只筛到√n且内层从i²开始：数组大小≥n+1，is_prime[0]和[1]置false，外层i≤√n，内层j从i²起步并检查j≤n，避免重复筛和溢出。
埃氏筛（Eratosthenes Sieve）怎么写才不超时
埃氏筛的核心是：从 2 开始，把每个素数的倍数全部标记为合数。关键不是“筛多少”，而是“别重复筛”。常见错误是内层循环从 i * i 开始却忘了加边界检查，或用 int 存大数导致溢出。
正确写法要点：
- 数组大小必须 ≥
n + 1，下标直接对应数字，is_prime[0]和is_prime[1]初始化为false - 外层只遍历到
sqrt(n)（即i * i ），再大就无新倍数可筛 - 内层从
i * i开始标记，因为更小的倍数（如2*i,3*i）已被更小的素数筛过 - 用
vector<bool></bool>节省内存，但注意它不是标准容器——若需取地址或迭代器操作，换vector<char></char>
vector<char> sieve_eratosthenes(int n) {
vector<char> is_prime(n + 1, 1);
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
for (long long j = (long long)i * i; j <= n; j += i) {
is_prime[j] = 0;
}
}
}
return is_prime;
}欧拉筛（线性筛）为什么能 O(n)？关键在“最小质因子”
欧拉筛不是“每个合数被所有质因子筛”，而是“每个合数只被它的最小质因子筛一次”。这靠两个判断实现：当 i % primes[j] == 0 时立刻 break。否则会用更大的质数去筛同一个数，破坏线性。
常见误写：
立即学习“C++免费学习笔记（深入）”；
- 没在
i % primes[j] == 0后break→ 变成埃氏筛，时间退化为 O(n log log n) - 内层循环条件写成
j → 逻辑错，应是 <code>primes[j] * i - 用
int计算primes[j] * i溢出 → 必须转long long判断上界
vector<char> sieve_euler(int n) {
vector<char> is_prime(n + 1, 1);
vector<int> primes;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) primes.push_back(i);
for (int j = 0; j < (int)primes.size(); ++j) {
long long p = (long long)primes[j] * i;
if (p > n) break;
is_prime[p] = 0;
if (i % primes[j] == 0) break;
}
}
return is_prime;
}埃氏筛 vs 欧拉筛：什么时候该选哪个
欧拉筛理论快，但常数大、缓存不友好；埃氏筛简单、局部性好，实际在 n ≤ 1e7 时往往更快。别盲目追求“O(n)”。
- 选埃氏筛：只要求快速预处理、n 在 1e6～1e7、代码要短且易 debug
- 选欧拉筛：n ≥ 1e8、需要同时获取质数列表、题目强制卡常（如 ACM 现场赛）、后续要频繁查第 k 个素数
- 都别用：n > 1e9 → 改用分段筛（segmented sieve）或 Miller-Rabin 随机测试
内存方面，两者都是 O(n)，但欧拉筛多一个 primes 数组，约存 π(n) ≈ n / ln n 个 int，对 1e8 就多占 ~5MB。
真实项目中容易忽略的细节
竞赛或工程里，筛法不是“写完就跑”，常卡在边界和类型上：
-
n = 0或n = 1时，埃氏筛的i * i 不进循环，但 <code>is_prime大小仍要 ≥n + 1，否则访问越界 - 用
vector<bool></bool>返回后，不能对元素取地址（&is_prime[i]是非法的），调试时容易段错误 - 多线程环境下，埃氏筛可并行外层（每个线程负责一段 i），但欧拉筛必须串行——它依赖
primes的实时增长 - 如果只需判断单个大数是否为素数，筛法完全不合适，应直接试除到 sqrt(n) 或用
std::is_prime（C++20）
最麻烦的其实是“筛完怎么用”：比如要统计 [L, R] 内素数个数，别急着开 1e9 大小数组——先筛 √R，再用分段筛更稳妥。
