17370845950

小于2的数（0、1）不是素数；2是唯一偶素数；其余偶数直接返回false；后续只需检查奇数因子，可节省约一半时间。

判断素数前先处理边界和偶数

小于 2 的数（0、1）不是素数；2 是唯一偶素数，其余偶数直接返回 false。跳过所有偶数能省一半时间，这是最基础但常被忽略的剪枝。

• if (n
• if (n == 2) return true;
• if (n % 2 == 0) return false;

试除法只用检查到 sqrt(n)

若 n 有大于 sqrt(n) 的因子，则必对应一个小于 sqrt(n) 的因子。因此循环上限取 int(sqrt(n)) + 1 即可，避免浮点误差建议用 i * i 判断。

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

6k±1 优化适用于多次调用场景

除 2 和 3 外，所有素数都形如 6k ± 1（因为其他形式必被 2 或 3 整除）。该规律可用于跳过更多合数，但单次判断收益有限，适合预生成小素数表或高频调用时使用。

• 先特判 n == 2 || n == 3
• 再排除 n % 2 == 0 || n % 3 == 0
• 循环从 i = 5 开始，每次检查 i 和 i + 2，然后 i += 6

注意 int 溢出和类型转换陷阱

当 n 接近 INT_MAX 时，i * i 中的 i * i 可能溢出为负数，导致死循环。安全写法是

• 错误： for (int i = 3; i * i （n = 2147483647 时 i=46341 会溢出）
• 正确： for (int i = 3; i
• 更稳妥： for (long long i = 3; i * i

实际用哪个方法，取决于你调用频率、输入范围和是否允许额外空间。单次判断用 i 版本最稳；批量筛素数就别手写试除，直接上埃氏筛或线性筛。