欧拉筛

欧拉筛法是一种高效的质数筛法，可以在线性时间内筛出一定范围内的所有质数。它的基本思想是遍历每个数，如果它是质数就把它的倍数都标记为合数。不同于普通的筛法，欧拉筛法在标记合数时采用了质数分解的思想，即每个数只会被最小的质因子筛掉，这样可以保证每个数只被筛一次，从而达到线性复杂度。

简介

筛法进行复杂度优化，所采用的一个惯用思路是：找到一个素数后，就将它的倍数标记为合数，也就是把它的倍数“筛掉”；如果一个数没有被比它小的素数“筛掉”，那它就是素数。欧拉筛法的大致思路也是如此，就是其中有些细节有差异。欧拉筛法拥有 线性的复杂度，而且编码较简单，应用十分广泛。

做法

假设要筛出 $n$ 以内的素数。我们先把所有数标记为素数。枚举 $i$ 从 $2$ 到 $n$，所以因为 $i$ 是从小到大的，如果 $i$ 没有被前面的数（比它小的数）标记为合数，那 $i$ 就是素数，加入素数列表。现在用 $i$ 来筛后面的数，枚举已经筛出来的素数 $prime[j]（j=1-cnt）$，标记 $i * prime[j]$ 为合数，且当 $i$ 是 $prime[j]$ 的倍数时（$prime[j]$ 是 $i$ 的最小质因数）退出循环，i++。

正确性

假设我们要筛掉合数 $a$，且 $a$ 的最小质因数为 $p_1$，令 $a = p_1b$，那么显然$b <a$，$b$ 先被外层循环碰到。现在 $b$ 要筛掉它与一些质数的积。因为 $p_1$ 是 $a$ 的最小质因数，所以 $b$ 的最小质因数必不小于 $p_1$，这样就保证 $b$ 在筛掉 $a=p_1b$ 前不会跳出循环。即使 $b$ 的最小质因数等于 $p_1$ ，也会先筛掉 $a$ 后再退出循环。这样就保证了每个合数都会被筛掉。

代码

从 jiangly 的代码里抠下来的欧拉筛板子，$minp[i]$ 数组的设置很巧妙，表示 $i$ 的最小质因数。

#include <bits/stdc++.h>
using namespace std;
const int M = 1e5;
int minp[M + 5];
vector<int> primes;
int main() {
    for (int i = 2; i <= M; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > M)
                break;
            minp[i * p] = p;
            if (minp[i] == p)
                break;
        }
    }
    return 0;
}