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 < N; ++i) {
if (!is_composite[i]) {
for (size_t j = i * i; j < N; j += i) {
is_composite[j] = true;
}
}
}-
N必须是编译时常量，不能是运行时变量（否则编译失败） - 内层循环起始用
i * i而非2 * i，避免重复标记 - 外层上限用
i * i < N，比i <= sqrt(N)更安全（避免浮点误差和类型转换）
std::bitset 筛法的性能陷阱与替代方案
当 N 很大（比如 > 1e8）时，std::bitset<N> 会占用约 N/8 字节内存，可能超出栈空间（默认栈有限），导致段错误。此时必须用堆分配：
auto sieve = std::make_unique<std::bitset<10000000>>(); // 放堆上 (*sieve)[0] = (*sieve)[1] = true; // ... 后续操作同上
但更大的问题是：std::bitset 不支持动态大小，也无法像 std::vector<bool></bool> 那样用 resize()。若需运行时决定筛范围，只能用 std::vector<bool></bool> 或手动管理 std::vector<unsigned char> —— 前者虽有代理迭代器开销，但更灵活；后者最省内存但编码复杂。
立即学习“C++免费学习笔记（深入）”；
-
std::bitset的count()可快速统计质数个数，比遍历std::vector快 - 用
any()/none()检查某段是否有合数，但实际筛法中很少需要 - 不要试图用
to_string()输出整个筛结果——字符串长度是N，极易爆内存
提取质数结果时下标与数值的对应关系
最容易忽略的是：std::bitset 的下标就是数值本身，但很多人误以为要偏移。例如想获取所有 ≤ 100 的质数，就直接遍历下标 2 到 100：
for (size_t i = 2; i <= 100; ++i) {
if (!is_composite[i]) {
std::cout << i << " ";
}
}如果想把质数存入容器，注意 std::bitset::size() 返回的是模板参数 N，不是实际有效范围。若筛的是 [0, N)，则有效数值范围就是 [0, N)，无需额外减一或加一。
- 不要写
if (!is_composite.test(i))—— 直接!is_composite[i]更高效（test()有函数调用开销） - 如果
N不是 8 的倍数，std::bitset仍会按字节对齐分配，但逻辑长度仍是N，不必担心“末尾废位”影响逻辑 - 多线程下不能共享修改同一个
std::bitset，没有原子位操作支持
实际写的时候，先确认 N 是否固定、是否够大、是否允许栈分配——这三个条件缺一，std::bitset 就不是最优选。
