is_prime函数采用6k±1优化最实用：跳过2和3的倍数，仅检查6k-1和6k+1形式的候选因子，比奇数试除快约1/3，但需注意边界处理和循环条件。
单个数判断用 is_prime：6k±1 优化最实用
对单个整数做素性判断，is_prime 函数用 6k±1 优化是平衡可读性与性能的首选。它跳过所有 2 和 3 的倍数，只检查形如 6k-1 和 6k+1 的候选因子，比纯奇数试除再快约 1/3。
常见错误是漏掉边界处理或写错循环条件：
n 必须返回 <code>false；n == 2 || n == 3要直接返回true- 别用
sqrt(n)开浮点根再转 int——浮点误差可能导致漏判，改用i * i - 循环起始值必须是 5，步长为 6；每次检查
i和i + 2（即 6k−1 和 6k+1）
示例实现：
bool is_prime(int n) {
if (n <h3>大数（≥10⁹）要用 <code>Miller-Rabin</code>，不是试除</h3><p>当 <code>n</code> 接近 <code>int64_t</code> 上限（比如 10¹⁸），<code>is_prime</code> 即使是 6k±1 版也会超时——因为最坏仍要循环约 10⁹ 次。此时必须换 <code>Miller-Rabin</code>。</p><p>关键点不是“概率算法”，而是对 uint64_t 范围，用固定底数集 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 可做到 100% 确定性判断。</p><p>容易踩的坑：</p>
- 快速幂中
(a * b) % mod直接相乘会溢出——必须用__int128（GCC）或自实现模乘 - 没单独处理
n 、<code>n == 2、偶数，导致n=1或n=4判错 - 只测一个底数就返回
true，实际需对全部 7 个底数都通过才算素数
批量查素数？别调 is_prime 循环，用埃氏筛预处理
如果你要判断 [2, 10⁶] 内 10⁴ 个数是否为素数，反复调用 is_prime 是灾难——总操作量可能达 10¹⁰ 级。此时应一次性用埃氏筛生成布尔表。
实操要点：
-
vector<bool> is_prime(n + 1, true)</bool>初始化后，立刻设is_prime[0] = is_prime[1] = false - 外层循环上限是
sqrt(n)，但写成i * i 更安全 - 内层标记从
i * i开始，不是i * 2——更小的倍数已被更小素数筛过 - 别在筛的过程中
push_back素数列表，缓存不友好；筛完再遍历收集
示例片段：
int n = 1000000; vector<bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <h3> <code>vector<bool></bool></code> 看似省空间，但访问慢</h3> <p><code>vector<bool></bool></code> 是 C++ 标准库特化类型，底层用位压缩，空间省 8 倍，但每次读写都要位运算，随机访问比 <code>vector<char></char></code> 慢 2–3 倍。对性能敏感且内存充足时，直接用 <code>vector<char></char></code> 更稳。</p> <p>尤其在筛法中，内层循环频繁读写 <code>is_prime[j]</code>，这个差异会放大。OJ 上跑 10⁶ 筛，<code>vector<char></char></code> 常比 <code>vector<bool></bool></code> 快 10–20ms。</p> <p>改法很简单：</p> <ul> <li>声明换成 <code>vector<char> is_prime(n + 1, 1)</char></code> </li> <li>赋值用 <code>is_prime[j] = 0</code>，判读用 <code>if (is_prime[i])</code> </li> <li>别忘了初始化 <code>is_prime[0] = is_prime[1] = 0</code> </li> </ul> <p>真正影响性能的，往往不是算法理论复杂度，而是 cache 行命中和分支预测——这点容易被忽略。</p></bool>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
