如何用C++编程实现两种不同的方法来判断一个大于2的正整数n是否为素数？

在C++中，判断一个大于2的正整数n是否为素数可以采用两种常见的方法：

1. **试除法**（也称为暴力法）：这是最直观的方法，遍历从2到√n的所有整数，如果n能被其中任何一个数整除，那么n不是素数。代码示例如下：

#include <cmath>
bool isPrime(int n) {
    if (n <= 1 || (n > 2 && n % 2 == 0)) {
        return false;
    }
    for (int i = 3; i * i <= n; i += 2) { // 只需检查奇数因子
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

2. **埃拉托斯特尼筛法**：这是一种优化过的算法，适用于大量数据。它创建一个数组，并标记所有的非素数，然后仅保留那些未标记的作为素数。这种方法对于大范围内的素数查找更有效率。以下是简单的实现：

void sieveOfEratosthenes(int n, bool primes[n+1]) {
    memset(primes, true, sizeof(primes));
    primes[0] = primes[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i)
                primes[j] = false;
        }
    }
    for (int i = 2; i <= n; ++i)
        if (primes[i])
            isPrime(i) = true; // 如果在筛法后还标记为true，则是素数
}

bool isPrimeOptimized(int n) {
    if (n <= 1 || (n > 2 && n % 2 == 0))
        return false;
    bool* primes = new bool[n + 1];
    sieveOfEratosthenes(n, primes);
    delete[] primes;
    return primes[n]; // primes[n]将直接返回n是否为素数
}