c++中如何判断一个数是否为素数_c++判断质数的算法实现【指南】

穿越時空 2026-01-19 00:00:00 次阅读

只需试除到√n即可判断素数，因若n有大于√n的因数，则必有对应小于√n的因数；注意n=1、n=2等边界情况需单独处理。

用 `sqrt(n)` 优化试除法判断素数

直接从 2 试除到 n-1 效率太低，多数情况下没必要。真正只需检查到 sqrt(n) —— 因为如果 n 有大于 sqrt(n) 的因数，那它一定对应一个小于 sqrt(n) 的因数。

注意边界处理：n 不是素数；n == 2 是唯一偶素数；所有其他偶数可直接返回 false。

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {  // i*i 避免浮点 sqrt，且只试奇数
        if (n % i == 0) return false;
    }
    return true;
}

处理大整数时的溢出风险

i * i 在 n 接近 INT_MAX 时，i * i 可能溢出变成负数，导致循环失控或误判。安全做法是改用 i （整除）。

n / i 是整数除法，不会溢出，且语义等价于 i
当 i > n / i 时，说明 i * i > n，可安全退出
对 long long 类型也适用，无需额外类型转换

bool is_prime(long long n) {
    if (n <= 1) 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;
}