欧拉筛c++算法讲解

欧拉筛(Euler's Sieve)是一种用于找出一定范围内所有质数的经典算法。它基于埃拉托斯特尼筛法（Sieve of Eratosthenes），但是采用了更有效的策略来避免重复工作。以下是基本的C++实现：

#include <vector>
using namespace std;

void erastoSieve(int limit, vector<int>& primes) {
    bool isPrime[limit + 1]; // 初始化所有数为true
    fill(isPrime, isPrime + limit + 1, true);

    for (int p = 2; p * p <= limit; ++p) { // 只需检查到√limit
        if (isPrime[p]) {
            for (int i = p * p; i <= limit; i += p) // 将p的倍数标记为非质数
                isPrime[i] = false;
        }
    }

    for (int p = 2; p <= limit; ++p)
        if (isPrime[p])
            primes.push_back(p); // 将剩余的质数添加到结果数组
}

// 使用示例
int main() {
    int limit = 100; // 想要查找的质数范围
    vector<int> primes;
    erastoSieve(limit, primes);
    
    // 打印找到的所有质数
    for (const auto& prime : primes)
        cout << prime << " ";
    return 0;
}

这个算法首先创建一个布尔数组表示每个数是否为质数，然后从最小的素数开始，将它的所有倍数标记为非质数。最后，剩下的未标记为非质数的数就是质数。