埃氏筛法核心是批量标记合数而非逐个验证，内存上筛100万以内素数用vector仅需约125kb；其易错点包括数组大小应为n+1、外层循环上限取√n且用i*i避免越界、不可对vector取地址或用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，常见错误全集中在下标和终止条件上：
- 数组大小必须是
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 <h3>提取素数结果时注意 vector 的 reserve 和移动语义</h3> <p>100万以内共78498个素数，如果边筛边 <code>push_back</code> 而不预留空间，vector 会多次重新分配——每次复制已有数据，白白消耗毫秒级时间。</p> <ul> <li>提前调用 <code>primes.reserve(80000)</code>（略大于理论值，避免扩容）</li> <li>提取时用 <code>primes.push_back(i)</code>，别用 <code>primes.emplace_back(i)</code>——整数无构造开销，<code>push_back</code> 更直白</li> <li>如果后续只读不改，考虑用 <code>std::vector<int> const&</int></code> 接收结果，避免意外修改</li> </ul> <p>最后生成的 <code>primes</code> 向量，首元素是 <code>2</code>，末元素是 <code>999983</code>，长度严格为 <code>78498</code>。这个数字本身就能帮你快速验证筛法是否漏数或多筛。</p></bool>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
