C++素数测试方法的比较

在C++中，有多种方法可以用来测试一个数是否为素数。以下是一些常见的方法的比较：

1. 穷举法：穷举法是最简单的方法，即对于一个数n，从2开始逐个检查是否能整除n。这种方法的时间复杂度为O(n)，效率较低。

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

2. 优化的穷举法：在穷举法的基础上，可以进行一些优化，比如只需要检查到sqrt(n)即可，因为如果n有一个大于sqrt(n)的因子，那么一定有一个小于sqrt(n)的因子。这种方法的时间复杂度为O(sqrt(n))，略有提升。

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

3. 厄拉托斯特尼筛法：厄拉托斯特尼筛法是一种更高效的方法，可以筛选出一定范围内的所有素数。其基本思想是从2开始，不断地将其倍数标记为非素数，从而剔除非素数。这种方法的时间复杂度为O(nloglogn)，效率最高。

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

根据以上的比较，可以看出厄拉托斯特尼筛法是最有效的方法，适用于筛选一定范围内的所有素数，而在单个数的素数测试中，优化的穷举法可能是更好的选择。