C++ 怎么判断素数 C++ 质数筛选算法效率优化【数学】_技术教程

is_prime函数通过特判n

怎么用 `is_prime` 快速判断单个数是否为素数

对单个整数做素性判断，最直接的方式是试除法：检查从 2 到 √n 是否有能整除 n 的数。但要注意几个关键点：

必须特判 n （0、1 不是素数），n == 2 直接返回 true
偶数只需检查 n == 2，其余偶数直接返回 false，避免一半无谓循环
循环起点设为 3，步长为 2，只试奇数因子
上界用 i * i 而非 i ，避免浮点误差和 sqrt 调用开销

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;
}

筛到 10⁶ 以内用 `std::vector` 做埃氏筛就够了

当需要批量判断 [2, N] 内所有数是否为素数，埃拉托斯特尼筛法（埃氏筛）简单可靠。对 N ≤ 10⁶，用 std::vector 即可，空间紧凑且缓存友好：

初始化全为 true，is_prime[0] 和 is_prime[1] 设为 false
外层循环只需到 √N；内层从 i * i 开始标记，因为更小的倍数已被更小的质数筛过
避免使用 vector 或 bitset（除非 N > 10⁷），前者浪费空间，后者在小规模下无明显优势且语法冗余

std::vector sieve(int n) {
    std::vector is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

筛到 10⁷ 以上建议改用线性筛（欧拉筛）

埃氏筛时间复杂度是 O(N log log N)，而线性筛能做到严格 O(N)，关键在于每个合数只被其最小质因子筛一次。它适合 N ≥ 10⁷ 且内存允许的情况：

维护一个质数列表 primes 和一个最小质因子数组 min_prime（或仅
用 is_prime + 额外逻辑）
内层循环中，一旦发现 i % primes[j] == 0，立刻 break —— 这保证了后续更大的质数不会用来筛 i * primes[j]，否则最小质因子就不是 primes[j]
注意数组大小要开到 N+1，且 primes 容量预留足够（π(N) ≈ N / ln N）

std::vector linear_sieve(int n) {
    std::vector is_prime(n + 1, true);
    std::vector primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
    return primes;
}