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

别在运行时反复调用 is_prime 判断大量数字

如果问题本质是「查询多

个数是否为素数」，比如输入 10⁵ 个数分别判断，哪怕单次 is_prime 是 O(√n)，最坏情况可能超时（例如全为 10⁹ 附近的大数）。这时应：

• 先收集所有待查数，取最大值 max_n
• 若 max_n ≤ 10⁶，直接筛出 [2, max_n] 的素数表，O(1) 查询
• 若 max_n > 10⁶ 但查询数不多（如 ≤ 10⁴），仍可用优化版 is_prime，但务必加 6k±1 优化（跳过所有 2、3 的倍数）
• 注意：6k±1 优化需额外特判 2 和 3，且循环步长变成 6，起始点为 5 和 7

很多人卡在“以为单次试除够快”，实际数据一多，缓存不友好 + 重复开方 + 偶数未剪枝，性能会断崖式下跌。