欧拉筛c++

欧拉筛（Euler's Sieve）是一种用于快速筛选素数的算法，其时间复杂度为 $O(n)$，与线性筛法相同。以下是C++代码示例：

const int MAXN = 1e6 + 5;
int prime[MAXN], tot; // 存储素数以及素数个数
bool isPrime[MAXN]; // 标记是否为素数

void EulerSieve(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) prime[++tot] = i;
        for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) break;
        }
    }
}

在上述代码中，我们首先初始化数组 `isPrime` 为 `true`，然后将 `0` 和 `1` 标记为非素数。之后从 $2$ 开始遍历，如果当前数是素数，我们将其加入 `prime` 数组中。接着从小到大枚举 `prime` 数组中的素数，将 `i` 与其乘积小于等于 $n$ 的合数标记为非素数，这里采用了类似于线性筛法的方式，保证每个数只被标记一次。最后得到的 `prime` 数组即为 $1 \sim n$ 中的所有素数，而 `tot` 记录的就是素数的个数。