欧拉筛法示例代码C++

欧拉筛法是一种用于找出所有小于给定数n的素数的高效算法。这里是一个简单的C++代码示例：

#include <iostream>
#include <vector>

using namespace std;

void sieveOfEuler(int n) {
    vector<bool> primes(n+1, true); // 初始化一个布尔数组，所有的元素都是true表示它们可能是素数
    primes[0] = primes[1] = false; // 0和1不是素数

    for (int i = 2; i * i <= n; i++) { // 只需检查到√n
        if (primes[i]) { // 如果i是素数
            for (int j = i * i; j <= n; j += i) { // 将i的倍数标记为非素数
                primes[j] = false;
            }
        }
    }

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

int main() {
    int limit;
    cout << "请输入一个正整数n: ";
    cin >> limit;
    cout << "小于" << limit << "的素数是:\n";
    sieveOfEuler(limit);
    return 0;
}

在这个示例中，程序首先创建一个布尔数组`primes`，然后从2开始遍历到√n。如果当前元素`i`是素数，就将它的所有倍数设为非素数。最后打印出所有未标记为非素数的数字就是素数。