欧拉筛代码函数 c++

欧拉筛（Sieve of Eratosthenes）是一种用于找出一定范围内所有质数的经典算法。在C++中实现欧拉筛通常会涉及动态规划的思想，通过标记数组来逐步排除非质数的因子。下面是一个简单的欧拉筛的代码示例：

#include <iostream>
#include <vector>

using namespace std;

void sieveOfEratosthenes(int n, vector<int>& primes) {
    // 初始化布尔数组，所有数字最初被视为质数
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false; // 0和1不是质数

    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) { // 如果i是质数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false; // 标记i的倍数为合数
            }
        }
    }

    // 将所有的质数存入primes向量
    for (int p = 2; p <= n; ++p) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }
}

int main() {
    int n;
    cout << "Enter the upper limit: ";
    cin >> n;
    
    vector<int> primes;
    sieveOfEratosthenes(n, primes);

    cout << "Primes up to " << n << ": ";
    for (const auto& prime : primes) {
        cout << prime << " ";
    }

    return 0;
}

在这个代码中，`sieveOfEratosthenes`函数接收两个参数，一个是范围上限n，另一个是结果存储的质数向量。它首先创建一个布尔数组表示每个数是否是质数，然后从2开始遍历到sqrt(n)，对每个质数的倍数标记为合数。最后，将未被标记为合数的数添加到primes向量。