std::bitset适合筛素数因其以位为单位存储布尔状态，空间紧凑且支持高效批量位操作；但大小需编译期确定，适用于固定上限的埃氏筛，需正确处理边界（如从i²开始标记、预留0/1）。
std::bitset 为什么适合筛素数
因为筛法本质是布尔标记——每个数对应一个“是否为合数”的开关，std::bitset以位为单位存储，空间比 std::vector<bool></bool> 更紧凑（通常 1 bit/元素），且支持批量位操作（如 set()、reset()、flip()），对连续区间清零或置位比逐个赋值快得多。但要注意：它的大小必须在编译期确定，所以筛上限得是常量表达式。
如何用 std::bitset 实现埃氏筛（含边界处理）
常见错误是越界访问或漏筛 2 的倍数。正确做法是：从 2 开始，只遍历到 sqrt(N)，对每个未被标记的 i，从 i*i 开始标记其倍数（因为更小的倍数已被更小的质数筛过）。std::bitset 下标从 0 开始，所以通常让下标 i 对应数值 i，并预留位置 0 和 1：
constexpr size_t N = 1000000; std::bitset<n> is_composite; // is_composite[i] == true 表示 i 是合数 is_composite[0] = is_composite[1] = true; for (size_t i = 2; i * i <ul> <li> <code>N</code> 必须是编译时常量，不能是运行时变量（否则编译失败）</li> <li>内层循环起始用 <code>i * i</code> 而非 <code>2 * i</code>，避免重复标记</li> <li>外层上限用 <code>i * i ，比 <code>i 更安全（避免浮点误差和类型转换）</code></code> </li> </ul> <h3>std::bitset 筛法的性能陷阱与替代方案</h3> <p>当 <code>N</code> 很大（比如 > 1e8）时，<code>std::bitset<n></n></code> 会占用约 <code>N/8</code> 字节内存，可能超出栈空间（默认栈有限），导致段错误。此时必须用堆分配：</p> <pre class="brush:php;toolbar:false;">auto sieve = std::make_unique<:bitset>>(); // 放堆上 (*sieve)[0] = (*sieve)[1] = true; // ... 后续操作同上</:bitset>
但更大的问题是：std::bitset 不支持动态大小，也无法像 std::vector<bool></bool> 那样用 resize()。若需运行时决定筛范围，只能用 std::vector<bool></bool> 或手动管理 std::vector<unsigned char></unsigned> —— 前者虽有代理迭代器开销，但更灵活；后者最省内存但编码复杂。
-
std::bitset的count()可快速统计质数个数，比遍历std::vector快 - 用
any()/none()检查某段是否有合数，但实际筛法中很少需要 - 不要试图用
to_string()输出整个筛结果——字符串长度是N，极易爆内存
提取质数结果时下标与数值的对应关系
最容易忽略的是：std::bitset 的下标就是数值本身，但很多人误以为要偏移。例如想获取所有 ≤ 100 的质数，就直接遍历下标 2 到 100：
for (size_t i = 2; i <p>如果想把质数存入容器，注意 <code>std::bitset::size()</code> 返回的是模板参数 <code>N</code>，不是实际有效范围。若筛的是 [0, N)，则有效数值范围就是 [0, N)，无需额外减一或加一。</p>
- 不要写
if (!is_composite.test(i))—— 直接!is_composite[i]更高效（test()有函数调用开销） - 如果
N不是 8 的倍数，std::bitset仍会按字节对齐分配，但逻辑长度仍是N，不必担心“末尾废位”影响逻辑 - 多线程下不能共享修改同一个
std::bitset，没有原子位操作支持
实际写的时候，先确认 N 是否固定、是否够大、是否允许栈分配——这三个条件缺一，std::bitset 就不是最优选。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
