埃氏筛法求素数 c++

埃拉托斯特尼筛法（Sieve of Eratosthenes），也称欧几里得筛法，是一种古老的用于寻找一定范围内所有质数的经典算法。在C++中，它通常通过动态数组实现。以下是简单的步骤：

1. 初始化一个大小为n+1的布尔型数组isPrime[]，其中isPrime[i]表示i是否是质数。默认初始化为true，因为从2到n的所有数字都被认为可能是质数。

2. 遍历从2开始到√n（取整），对于每个质数p：
a. 如果isPrime[p]为true，说明p尚未被标记为合数，将它的倍数全部设为false。从p^2开始，每次加p，直到超过n为止。

3. 经过上述过程后，isPrime[]数组中的值为true的就是质数。因为除了2以外的偶数不是质数，所以我们可以直接跳过2，仅检查奇数。

以下是一个简单的C++实现示例：

#include <iostream>
#include <vector>

std::vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;

    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    // 将索引转换为实际数值并返回质数列表
    std::vector<int> primes;
    for (int p = 2; p <= n; ++p)
        if (isPrime[p])
            primes.push_back(p);

    return primes;
}

int main() {
    int n;
    std::cout << "Enter the number up to which you want to find prime numbers: ";
    std::cin >> n;
    std::vector<int> primes = sieveOfEratosthenes(n);
    std::cout << "Prime numbers up to " << n << ": ";
    for (const auto& prime : primes)
        std::cout << prime << " ";
    return 0;
}