埃氏筛需开大小为n+1的数组，索引0到n；外层循环至√n，注意i*i不越界。常见错误是数组开n导致is_prime[n]访问非法或漏判。
埃氏筛的正确写法和常见越界错误
埃氏筛的核心是标记合数，但很多人一上来就开 vector<bool></bool> 到 n+1 却从 2 开始筛，漏掉边界处理，导致访问 is_prime[n] 时越界或漏判。
- 数组/容器大小必须是
n + 1（索引 0 到 n），否则is_prime[n]访问非法 - 外层循环只需到
sqrt(n)，但要注意i * i 比 <code>i 更安全（避免浮点误差和类型转换） - 内层标记从
i * i开始，不是2 * i——因为更小的倍数已被更小的质数筛过 -
vector<bool></bool>是特化模板，可能不支持取地址或迭代器随机访问；调试时建议先用vector<int></int>验证逻辑
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
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] = false;
}
}
}欧拉筛（线性筛）为什么必须用 vector 存质数
欧拉筛的关键是每个合数只被其最小质因子筛一次，这依赖于「遇到能整除的质数就 break」这一逻辑。如果不用显式质数列表，就无法控制筛除顺序和终止条件。
- 必须维护一个
primes容器（通常为vector<int></int>），用于按序记录已发现的质数 - 内层循环中，
i % primes[j] == 0时必须break，否则后续更大的质数会重复筛同一个数 - 注意
primes[j]可能大于sqrt(i)，但只要primes[j] * i 就继续筛，这是线性复杂度的保障 - 乘法溢出风险高：
primes[j] * i建议转成long long判断是否超n
vector<bool> is_prime(n + 1, true);
vector<int> primes;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) primes.push_back(i);
for (int p : primes) {
if ((long long)p * i > n) break;
is_prime[p * i] = false;
if (i % p == 0) break;
}
}bool 容器在筛法中的性能陷阱
vector<bool></bool> 看似省内存，但在筛法密集位操作中反而拖慢速度——它不是真正的容器，而是位压缩代理，operator[] 返回的是临时代理对象，不能取地址、不可迭代器遍历，且每次访问都带位运算开销。
- 在 n 较大（如 1e7）时，
vector<char></char>常比vector<bool></bool>快 10%~30%，因为缓存友好、无位拆包 - 如果后续还要遍历所有质数（比如输出或统计），
vector<bool></bool>强制你再扫一遍找true，而欧拉筛的primes向量天然有序且紧凑 - 调试阶段一律用
vector<int></int>或vector<char></char>，确认逻辑无误后再换vector<bool></bool>看是否真节省了内存
筛法结果怎么安全转成质数列表
筛完只是得到布尔标记，要拿到质数数组还得二次遍历，但很多人直接用 push_back(i) 而忽略 i 范围或类型匹配问题。
立即学习“C++免费学习笔记（深入）”；
- 遍历范围必须是
[2, n]，别漏掉n本身（尤其当n是质数时） - 如果原筛用
vector<bool></bool>，遍历时注意is_prime[i]返回的是vector<bool>::reference</bool>，虽可隐式转bool，但某些编译器优化下可能出未定义行为 - 更稳妥做法：筛完后统一用
vector<int> result</int>，只对is_prime[i]为真时push_back(i)，不要试图复用primes向量（除非你确定它是完整质数序列）
真正容易被忽略的是：筛法本身不保证质数有序输出——但埃氏筛和欧拉筛构造过程天然有序，所以只要按索引升序遍历，结果就是升序质数列。这点常被当成理所当然，但若中途修改逻辑（比如并行分段筛），顺序就得额外维护。
