std::bitset比vector更适合筛素数，因其编译期确定大小、内存连续、无动态分配开销，且底层直接支持高效位操作；而vector<bool>是特化模板，不支持取地址和随机迭代，访问慢15–20%，且调试时it+1非法属标准规定。
std::bitset 为什么比 vector 更适合筛素数
因为 std::bitset 是编译期确定大小的位容器，内存连续、无动态分配开销，且底层直接映射到位操作指令（如 _mm_popcnt_u64 在支持时可加速计数），而 vector<bool></bool> 是特化模板，行为不完全像容器，迭代器不可随机访问，部分实现中 flip() 或范围操作性能较差。筛素数这种需要大量单点设置/读取、且上限已知的场景，std::bitset 的常数级优势明显。
常见错误是用 std::vector<bool></bool> 替代，结果在 N=1e7 时慢 15–20%，且调试时发现 it + 1 不合法——这不是 bug，是标准规定。
- 必须在编译期知道最大值（比如筛到 10000000，就写
std::bitset） - 下标 0 和 1 默认标记为非素数，索引即数字本身，无需偏移映射
- 初始化后所有位为 0，需先置 0 和 1 为 1（表示合数），其余默认为 0（暂视为素数）
如何正确初始化并执行埃氏筛核心逻辑
关键不是“怎么写循环”，而是避免越界、重复标记和无效跳转。例如从 i*i 开始标记，但若 i*i > N 就不该进入内层；又比如步长用 i 而非 2*i（后者漏掉奇合数）。
constexpr size_t N = 10000000;
std::bitset<N + 1> is_composite;
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;
}
}
}-
i只需遍历到sqrt(N)，用i * i 判断，避免浮点 <code>sqrt引入精度与类型转换开销 - 内层
j从i*i启动：小于它的倍数已被更小的素因子筛过 - 不要对
i做额外奇偶判断——2会自然筛掉所有偶数，后续i=3,5,7...继续筛奇合数
如何安全地提取所有素数到 vector 中
不能直接用 std::copy_if 配合 std::count 做两趟遍历——虽然语义清晰，但对大 N（如 1e8）会显著拖慢。应单趟扫描 + 预分配空间，利用 is_composite.count() 得到合数个数，从而算出素数个数。
立即学习“C++免费学习笔记（深入）”；
- 调用
is_composite.count()是 O(N / word_size) 操作（通常为 O(N/64)），远快于逐位检查 - 素数数量 ≈
N / log(N)，但精确值用N + 1 - is_composite.count()最可靠 - 避免 push_back 导致多次 realloc：先
result.reserve(…)，再for (size_t i = 2; i 扫描
注意：is_composite.count() 返回的是 true 的个数（即合数+0+1），所以素数个数是 N - 1 - is_composite.count()（因为下标 0..N 共 N+1 个位置，减去两个合数标记，再减去合数总数）——更稳妥写法是：size_t prime_count = 0; for (size_t i = 2; i ，虽多一趟，但逻辑零歧义。
编译期大小限制与实际工程取舍
std::bitset 大小必须是编译期常量，意味着你无法用变量 int n 构造 std::bitset<n></n>。若输入上限不固定，硬编码如 std::bitset 会导致小数据浪费内存、大数据编译失败（栈溢出或模板实例爆炸）。
- 栈上定义大
bitset（如 >1MB）可能触发栈溢出，应改用static或全局作用域，或std::unique_ptr<:bitset>></:bitset>（但后者失去栈效率） - Clang/GCC 对模板参数大小有限制（通常几百万位可行，千万位可能报错 "template instantiation depth"），可用
-ftemplate-depth=缓解，但非根本解 - 真实项目中，若上限不确定，建议 fallback 到
std::vector<uint64_t></uint64_t>手动分段位操作，或直接用boost::dynamic_bitset
真正卡住性能的往往不是算法复杂度，而是 cache line 对齐和内存访问模式——std::bitset 连续布局天然友好，但若你把筛表定义在函数内又没加 alignas(64)，某些 CPU 上仍可能因 false sharing 拖慢多线程版本。
