17370845950

sqrt(n) 是判断素数的性能分水岭：若n有大于√n的因数d，则必有对应小于√n的因数n/d，故只需试除2到⌊√n⌋；注意sqrt(n)为浮点数，直接int转换可能因精度丢失，建议用i*i≤n代替。

为什么 sqrt(n) 是判断素数的性能分水岭

暴力试除到 n-1 太慢，而试除到 sqrt(n) 足够：如果 n 有大于 sqrt(n) 的因数 d，那必有对应的小于 sqrt(n) 的因数 n/d。所以只需检查 2 到 floor(sqrt(n))。

注意：sqrt(n) 返回浮点数，直接转 int 可能因精度丢位（如 n = 1000000000000），建议用 i 替代 i 避免浮点误差和类型转换开销。

• n 直接返回 false
• n == 2 是唯一偶素数，单独返回 true
• n % 2 == 0 && n != 2 → false
• 后续只试除奇数：for (int i = 3; i

处理边界值：0、1、2、负数怎么算

C++ 标准中素数定义为「大于 1 的正整数」，因此：

• is_prime(-5)、is_prime(0)、is_prime(1) 全部应返回 false
• is_prime(2) 必须返回 true —— 它是素数，且是唯一偶素数
• 不加特判直接进循环会导致 2 被 i=2 整除误判为合数

常见错误写法：if (n 正确覆盖了负数、0、1；但漏掉对 2 的允许，必须在之后放行或提前返回。

完整可运行的 is_prime 函数（含 64 位整数兼容）

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

用 long long 支持大数（如 10^12 级别），循环条件 i 同时避免溢出和浮点误差。若确定输入始终在 int 范围，可用 int 提升 cache 局部性。

注意：该函数对单次查询高效，但批量判断（如筛 1~10⁶ 内所有素数）应改用埃氏筛或线性筛，否则重复开销太大。

调试时遇到 9、25、49 判错？检查循环起始和步长

典型错误是把奇数循环写成 for (int i = 3; i * i —— 当 n 很大时 i * i 可能溢出，导致未定义行为（尤其 int 下 i > 46340 就炸）。n / i 是更安全的替代。

• is_prime(9) 错判为 true？说明循环没执行到 i = 3，检查是否漏了 i = 3 或起始值设成了 5
• is_prime(1) 返回 true？说明没做 n 检查
• is_prime(2147483647)（INT_MAX）卡死？说明用了 i * i 且

  

  i 是 int，溢出后条件恒真

实际项目里，如果输入范围明确且较小，可以预处理小素数表加速前几轮判断；但多数场景下，上述函数已足够健壮。