c++编程求1e12中所有质数

在 C++ 中，寻找大范围内如 1e12 的所有质数是一个相对复杂的任务，因为直接枚举并检查每个数是否为质数效率低下。通常我们会采用更高效的算法，比如埃拉托斯特尼筛法 (Sieve of Eratosthenes) 或者米勒-拉宾素数检验 (Miller-Rabin primality test)。

**埃拉托斯特尼筛法**是一种适用于寻找一定范围内所有质数的经典算法，步骤如下：
1. 创建一个大小为 n+1 的布尔数组 isPrime，初始时全部设为 true。
2. 遍历从 2 到 sqrt(n)，对于每个质数 p，将它的倍数标记为非质数：isPrime[p*p...n] = false。
3. 最终，isPrime 数组中值为 true 的索引对应的数字就是质数。

**米勒-拉宾算法**虽然不是确定性的，但对大数判断足够高效，通过多次随机测试来判断一个数可能是质数的概率很高。它可以在较短的时间内筛选出大量大范围内的候选质数。

下面是一个简单的基于埃拉托斯特尼筛法的基本示例，但请注意，这个方法无法直接用于 1e12 这样的大整数，因为内存限制和计算复杂度太高：

#include <vector>
using namespace std;

void sieveOfEratosthenes(int limit) {
    vector<bool> isPrime(limit + 1, true);
    for (int p = 2; p * p <= limit; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= limit; i += p)
                isPrime[i] = false;
        }
    }

    // 输出所有的质数
    for (int p = 2; p <= limit; ++p) {
        if (isPrime[p])
            cout << p << " ";
    }
}

int main() {
    sieveOfEratosthenes(1e6); // 示例，实际操作应调整参数
    return 0;
}