c++如何判断一个数是否为素数_C++判断质数的几种算法

基础试除法：判断2到n-1是否能整除n；2. 优化试除法：只需检查2到√n；3. 跳过偶数：大于2的偶数非素数；4. 埃拉托斯特尼筛法：批量求素数高效。

判断一个数是否为素数（质数）是C++编程中常见的问题。素数是指大于1且只能被1和自身整除的自然数。下面介绍几种常用的算法，从简单到高效，适用于不同场景。

1. 基础试除法

最直观的方法是尝试用2到n-1之间的所有数去除n，如果存在能整除的数，则n不是素数。

bool isPrime(int n) {
    if (n     if (n == 2) return true;
    for (int i = 2; i         if (n % i == 0)
            return false;
    }
    return true;
}

这种方法逻辑清晰，但效率低，时间复杂度为O(n)，不适合大数判断。

2. 优化试除法：只检查到√n

如果n有一个大于√n的因数，那么必然有一个小于√n的对应因数。因此只需检查2到√n即可。

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

跳过偶数并只检查到√n，时间复杂度降为O(√n)，适合大多数实际应用。

3. 使用6k±1优化

除了2和3，所有素数都可以表示为6k±1的形式。可以利用这一点减少循环次数。

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

该方法进一步减少了需要检查的数，性能比前一种更好，尤其在处理大数时优势明显。

4. 筛法预处理：埃拉托斯特尼筛法

如果需要判断多个数是否为素数，可以预先生成素数表。使用埃氏筛一次性标记出范围内的所有合数。

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

适用于需要频繁查询素数的场景，预处理时间复杂度为O(n log log n)，查询为O(1)。

基本上就这些常用方法。小数据用优化试除法，大数据或多次查询考虑筛法。理解每种算法的适用场景，能写出更高效的代码。