1. 筛选法求素数的根本思想

筛选法求素数的本意就是：比 1 大的数要么是合数，要么是素数。我们只要对合数打上标记，剔除掉这些合数，剩下的自然就是素数了。

筛选法求素数有很多种方法，但是共同点都是一个反复跌打的过程：

1. 通过检查标记，判断出当前一个数是合数还是素数
2. 基于新找到的合数或者素数，对一批新的合数字打上标记

这两个步骤是交替进行的。在给新的合数打标记的过程中，不同的筛法是各不相同的。我们在学习它们的时候，要把握住其方法的理论基础，从数理层面理解和比较。

2. 埃氏筛

这是有希腊古代科学家埃拉托斯特尼提出来的方法。埃拉托斯特尼出生于公元前 276 年，在中国就是战国时代，可想而知，这个方法提出来的时候压根就没有电子计算机。计算机科学、算法科学并不是一门独立的学科，它本身基于数学，是数学的一个分支。

埃氏筛选法的核心思想是：素数的若干倍（2 倍或者以上）是合数。

因此，它的算法步骤是：

1. 没有合数标记的数是素数，一个没有标记的数就是素数
2. 找到新的素数之后，用素数乘以若干倍（2倍及以上），得到的是合数，打上合数标记

算法一开始是从 2 开始，2 是最小的素数，所以，$2 * 2$, $2 * 3$, $2 * 4$, ..., $2 * 100$, .... 得到了一批的素数，我们给这些数打上标记。

看完 2 之后，就轮到 3 ，3 是没有标记的，所以也是素数，所以，我们用 3 乘以若干倍，$3 * 3$, $3 * 4$, ..., $3 * 100$, .... 得到了一批的素数，我们给这些数打上标记。（3 的 2 倍之前在找到 3 这个素数的时候已经标记过）

然后轮到 4，之前找到素数 2 的时候，$2 * 2=4$，我们是给 4 打了标记的，所以 4 是合数。

......

找到素数 $i$ 的时候，可以可以给 $i * 2$，$i * 3$，$i * 4$，....，打标记，但是可以做一个改进，从 $i*i$ 开始，因为 $i*2$ 这个数已经在找到素数 2 的时候打过标记，$i * 3$是在找到素数 3 的时候打过标记.......一个合数，如果多次被打标记，就是重复无用功。

bool f[1000001];
int prime[1000001],tot=0;

// f 是标记数组，有标记的表示是合数，在运算前要抹掉所有标记
memset(f,0,sizeof f);

// 找 n 以内的素数
for(int i=2;i<=n;i++){
	if(!f[i]){
		// i 没有标记，所以它是素数
		prime[++tot] = i; // 放入 prime 数组

		// 从 i 出发，给 i 的倍数打上合数标记
		for(int j=i;1ll*j*i<=n;j++)
			f[i*j] = true;
	}
}

埃氏筛选法比较容易理解，但是一个合数会多次被打上标记，因此效率并非最佳。例如，我们找到素数 $5$ 的时候，给 $5*5$, $5*6$, $5*7$, $5*8$.... 打上标记，我们找到素数 $7$ 的时候，我们给 $7*7$, $7*8$, $7*9$ ...... 打上标记。所以，$5*7$, $5*14$, $5*21$ ..... 就是重复打了标记（这批数字的共同特点是 $35$ 的倍数）。

埃氏筛选法的时间复杂度是 $O(n \log {\log n})$

3. 线性筛

埃氏筛的时间复杂度是 $O(n \log {\log n})$，所以，这不是线性的。为了提升计算效率，我们希望找到一个算法：每个合数只打一次标记。

大数学家欧拉找到了这样的方法，这个算法叫线性筛，也叫欧拉筛，核心的思想是：每个合数都是被它最小的那个质因数筛掉。例如，$q=p_1*p_2*...*p_k$，其中 $p_1$，$p_2$，...，$p_k$ 是合数 $q$ 的质因数，其中 $p_1$ 最小，$q$ 是从 $p_2*p_3*...p_k$ 出发，乘以 $p_1$ 筛选掉的。

例如，我们针对 $24=2*2*2*3$，从 $24$ 出发，$2482=48$，我们就知道 $48$ 是合数。但是，我们不能从 $24*3=72$ 来筛选 $72$，因为 $3$ 比 $24$ 的最小质因数 $2$ 大。 $72=2*2*2*3*3$，所以，$72=2*36$，应该是从 $36$ 出发乘以 $2$ 划掉。

通过这种机制，任何一个合数 $q$，都可以分解成 $q=p_1*(q/p_1)$，其中 $p_1$ 是 $q$ 最小质因数。这种分解方式是唯一的，所以，筛选的过程不重复。

bool f[1000001];
int prime[1000001],tot=0;

// f 是标记数组，有标记的表示是合数，在运算前要抹掉所有标记
memset(f,0,sizeof f);

// 找 n 以内的素数
for(int i=2;i<=n;i++){
	if(!f[i]) prime[++tot] = i;
	// i 没有标记，所以它是素数。把指数 i 放入 prime 数组

	// 无论 i 是不是质数，都要执行下面这层循环
	// 从 i 出发，用 i * prime[j] 得到一个合数，打上合数标记
	for(int j=1;1ll*prime[j]*i<=n;j++){
		f[i*prime[j]] = true;
		if(i%prime[j]==0) break; // 整除中断
		// prime[j] 是 i 最小的质因数，不能枚举后面的 prime[j] 了，否则就会重复打标记
	}
}