埃氏筛法核心是批量标记合数而非逐个验证，内存上筛100万以内素数用vector<bool>仅需约125KB；其易错点包括数组大小应为N+1、外层循环上限取√N且用i*i避免越界、不可对vector<bool>取地址或用data()。
埃氏筛法的核心逻辑和内存开销预判
筛到100万以内素数，std::vector<bool></bool> 是最现实的选择——它能将内存压到约125KB，而用 std::vector<int></int> 或 std::vector<char></char> 会直接涨到4MB或1MB，不必要地拖慢缓存命中率。关键不是“能不能写出来”，而是“别让 vector<bool></bool> 的代理引用陷阱把你绕进去”。
为什么不能直接对 vector<bool></bool> 取地址或用指针遍历
vector<bool></bool> 是特化容器，内部按位存储，operator[] 返回的是临时 std::vector<bool>::reference</bool>，不是 bool&。这意味着：
- 写
&v[i]会编译失败（无法取代理对象的地址） - 用
auto* p = v.data()拿不到原始字节数组（data()在vector<bool></bool>中被禁用） - 想手动按字节操作？得用
std::vector<char></char>替代，但要接受1MB内存代价
实操建议：老老实实用 v[i] = true/false 赋值，别试图优化访问方式；循环用 size_t i = 2 开始，避免有符号/无符号混用警告。
筛法实现中三个易错边界条件
筛到 N = 1000000，常见错误全集中在下标和终止条件上：
立即学习“C++免费学习笔记（深入）”；
- 数组大小必须是
N + 1（索引 0～N），否则is_prime[1000000]越界 - 外层循环上限是
sqrt(N)，但要用i * i 判断，而非 <code>i ——后者引入浮点误差且慢 - 内层标记从
i * i开始，不是2 * i：因为更小的合数（如2*i,3*i）早已被更小的质数筛过
示例关键片段：
std::vector<bool> is_prime(N + 1, true);
is_prime[0] = is_prime[1] = false;
for (size_t i = 2; i * i <= N; ++i) {
if (is_prime[i]) {
for (size_t j = i * i; j <= N; j += i) {
is_prime[j] = false;
}
}
}提取素数结果时注意 vector 的 reserve 和移动语义
100万以内共78498个素数，如果边筛边 push_back 而不预留空间，vector 会多次重新分配——每次复制已有数据，白白消耗毫秒级时间。
- 提前调用
primes.reserve(80000)（略大于理论值，避免扩容） - 提取时用
primes.push_back(i)，别用primes.emplace_back(i)——整数无构造开销，push_back更直白 - 如果后续只读不改，考虑用
std::vector<int> const&接收结果，避免意外修改
最后生成的 primes 向量，首元素是 2，末元素是 999983，长度严格为 78498。这个数字本身就能帮你快速验证筛法是否漏数或多筛。
