C++欧拉筛法

欧拉筛法是一种高效的素数筛法，可以用于求解一定范围内的素数。以下是C++实现：

#include <iostream>
#include <vector>
using namespace std;

vector<int> eulerSieve(int n) {
    vector<int> primes;
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push_back(i);
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    return primes;
}

其中，`primes`数组存储筛出的素数，`isPrime`数组表示该数是否为素数。在循环中，我们先判断当前数是否为素数，如果是，则加入`primes`数组。然后，对于`primes`数组中的每一个素数`p`，将它与当前数`i`相乘，若结果不超过n，则将`isPrime[i * p]`标记为非素数。如果`i`能够整除`p`，则跳出内层循环，因为此时已经标记了所有小于等于`i`且含有`p`因子的数。

使用该算法求解n以内的素数，时间复杂度为O(nloglogn)。