欧拉筛输出1-100000的质数 c++代码

欧拉筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有质数的经典算法。下面是使用 C++ 实现的简单版本，它会输出1到100000之间的质数：

#include <iostream>
#include <vector>

// 将合 p[i] 的倍数标记为合数
void sieveOfEratosthenes(int n, std::vector<int>& primes) {
    primes.resize(n + 1);
    for (int i = 2; i * i <= n; ++i) {
        if (primes[i]) continue; // 如果 i 是质数，则跳过
        for (int j = i * i; j <= n; j += i) {
            primes[j] = 0;
        }
    }

    // 输出所有的质数
    for (int i = 2; i <= n; ++i) {
        if (primes[i]) {
            std::cout << i << " ";
        }
    }
}

int main() {
    int limit = 100000;
    std::vector<int> primes;
    sieveOfEratosthenes(limit, primes);
    return 0;
}

在这个代码里，我们首先初始化一个大小为 `n+1` 的布尔数组 `primes`，然后从2开始遍历，将每个素数的倍数标记为合数。最后只保留那些未被标记的数，即为质数。

运行此程序，它会在控制台上打印出1到100000范围内的所有质数。