std::bitset比vector更适合筛素数，因其编译期确定大小、内存连续、无动态分配开销，且底层直接支持高效位操作；而vector是特化模板，不支持取地址和随机迭代，访问慢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> is_composite; is_composite[0] = is_composite[1] = true; for (size_t i = 2; i * i <ul> <li> <code>i</code> 只需遍历到 <code>sqrt(N)</code>，用 <code>i * i 判断，避免浮点 <code>sqrt</code> 引入精度与类型转换开销</code> </li> <li>内层 <code>j</code> 从 <code>i*i</code> 启动：小于它的倍数已被更小的素因子筛过</li> <li>不要对 <code>i</code> 做额外奇偶判断——<code>2</code> 会自然筛掉所有偶数，后续 <code>i=3,5,7...</code> 继续筛奇合数</li> </ul> <h3>如何安全地提取所有素数到 vector 中</h3> <p>不能直接用 <code>std::copy_if</code> 配合 <code>std::count</code> 做两趟遍历——虽然语义清晰，但对大 <code>N</code>（如 1e8）会显著拖慢。应单趟扫描 + 预分配空间，利用 <code>is_composite.count()</code> 得到合数个数，从而算出素数个数。</p><div class="aritcle_card flexRow artxards"> <div class="artcardd flexRow"> <a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a> <div class="aritcle_card_info flexColumn"> <a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a> <p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p> </div> <a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span> </a> </div> </div> <ul> <li>调用 <code>is_composite.count()</code> 是 O(N / word_size) 操作（通常为 O(N/64)），远快于逐位检查</li> <li>素数数量 ≈ <code>N / log(N)</code>，但精确值用 <code>N + 1 - is_composite.count()</code> 最可靠</li> <li>避免 push_back 导致多次 realloc：先 <code>result.reserve(…)</code>，再 <code>for (size_t i = 2; i 扫描</code> </li> </ul> <p>注意：<code>is_composite.count()</code> 返回的是 true 的个数（即合数+0+1），所以素数个数是 <code>N - 1 - is_composite.count()</code>（因为下标 0..N 共 N+1 个位置，减去两个合数标记，再减去合数总数）——更稳妥写法是：<code>size_t prime_count = 0; for (size_t i = 2; i ，虽多一趟，但逻辑零歧义。</code></p> <h3>编译期大小限制与实际工程取舍</h3> <p><code>std::bitset</code> 大小必须是编译期常量，意味着你无法用变量 <code>int n</code> 构造 <code>std::bitset<n></n></code>。若输入上限不固定，硬编码如 <code>std::bitset</code> 会导致小数据浪费内存、大数据编译失败（栈溢出或模板实例爆炸）。</p> <ul> <li>栈上定义大 <code>bitset</code>（如 >1MB）可能触发栈溢出，应改用 <code>static</code> 或全局作用域，或 <code>std::unique_ptr<:bitset>></:bitset></code>（但后者失去栈效率）</li> <li>Clang/GCC 对模板参数大小有限制（通常几百万位可行，千万位可能报错 "template instantiation depth"），可用 <code>-ftemplate-depth=</code> 缓解，但非根本解</li> <li>真实项目中，若上限不确定，建议 fallback 到 <code>std::vector<uint64_t></uint64_t></code> 手动分段位操作，或直接用 <code>boost::dynamic_bitset</code> </li> </ul> <p>真正卡住性能的往往不是算法复杂度，而是 cache line 对齐和内存访问模式——<code>std::bitset</code> 连续布局天然友好，但若你把筛表定义在函数内又没加 <code>alignas(64)</code>，某些 CPU 上仍可能因 false sharing 拖慢多线程版本。</p></n>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
