使用埃式筛法写一个c++筛素数的程序

下面是一个使用埃式筛法（Sieve of Eratosthenes）写的C++程序，用于筛选素数：

#include <iostream>
#include <vector>

std::vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;

    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;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

int main() {
    int n;
    std::cout << "Enter the upper limit: ";
    std::cin >> n;

    std::vector<int> primes = sieveOfEratosthenes(n);

    std::cout << "Prime numbers up to " << n << " are: ";
    for (int prime : primes) {
        std::cout << prime << " ";
    }
    std::cout << std::endl;

    return 0;
}

该程序首先使用std::vector<bool>创建一个布尔数组isPrime，该数组的大小为n+1，并将所有元素初始化为true。然后，将isPrime[0]和isPrime[1]设为false，因为它们不是素数。

接下来，程序使用两个嵌套的循环，外循环从2开始，内循环从外循环变量的平方开始，每次增加外循环变量的值。在内循环中，将数组isPrime中的索引对应的元素设为false，表示该索引对应的数不是素数。

最后，程序遍历数组isPrime，将为true的索引对应的数添加到另一个std::vector<int>容器primes中。

在main()函数中，程序要求用户输入一个上限值n，然后调用sieveOfEratosthenes()函数得到小于等于n的所有素数，并将它们打印到控制台。

例如，如果用户输入上限值为10，程序将打印出小于等于10的所有素数：2 3 5 7