欧拉筛

先浏览如何实现再讲其中的原理。

实现

bool isPrime[1000001];
//isPrime[i] == 1表示：i是素数
int Prime[1000001], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
	memset(isPrime, 1, sizeof(isPrime));
	//以“每个数都是素数”为初始状态，逐个删去
	isPrime[1] = 0;//1不是素数
	
	for(int i = 2; i <= n; i++)
	{
		if(isPrime[i])//没筛掉 
			Prime[++cnt] = i; //i成为下一个素数
			
		for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
		{
        	//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
			isPrime[ i*Prime[j] ] = 0;
            
			if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
				break; //重要步骤。见原理
		}
	}
}

原理概述

代码中，外层枚举 (i = 1 o n)。对于一个 (i)，经过前面的腥风血雨，如果它还没有被筛掉，就加到质数数组 (Prime[]) 中。下一步，是用 (i) 来筛掉一波数。

内层从小到大枚举 (Prime[j])。(i×Prime[j]) 是尝试筛掉的某个合数，其中，我们期望 (Prime[j]) 是这个合数的最小质因数 (这是线性复杂度的条件，下面叫做“筛条件”)。它是怎么得到保证的？

(j) 的循环中，有一句就做到了这一点：

			if(i % Prime[j] == 0)
				break;

(j) 循环到 (i mod Prime[j] == 0) 就恰好需要停止的理由是：

下面用 (s(smaller)) 表示小于 (j) 的数，(L(larger)) 表示大于 (j) 的数。
① (i) 的最小质因数肯定是 (Prime[j])。

（如果 (i) 的最小质因数是 (Prime[s]) ，那么 (Prime[s]) 更早被枚举到（因为我们从小到大枚举质数），当时就要break）

既然 (i) 的最小质因数是 (Prime[j])，那么 (i × Prime[j]) 的最小质因数也是 (Prime[j])。所以，(j) 本身是符合“筛条件”的。
② (i × Prime[s]) 的最小质因数确实是 (Prime[s])。

（如果是它的最小质因数是更小的质数 (Prime[t])，那么当然 (Prime[t]) 更早被枚举到，当时就要break）

这说明 (j) 之前（用 (i × Prime[s]) 的方式去筛合数，使用的是最小质因数）都符合“筛条件”。
③ (i × Prime[L]) 的最小质因数一定是 (Prime[j])。

（因为 (i) 的最小质因数是 (Prime[j])，所以 (i × Prime[L]) 也含有 (Prime[j]) 这个因数（这是 (i) 的功劳），所以其最小质因数也是 (Prime[j])（新的质因数 (Prime[L]) 太大了））

这说明，如果 (j) 继续递增（将以 (i × Prime[L]) 的方式去筛合数，没有使用最小质因数），是不符合“筛条件”的。

小提示：

当 (i) 还不大的时候，可能会一层内就筛去大量合数，看上去耗时比较大，但是由于保证了筛去的合数日后将不会再被筛（总共只筛一次），复杂度是线性的。到 (i) 接近 (n) 时，每层几乎都不用做什么事。

建议看下面两个并不复杂的证明，你能更加信任这个筛法，利于以后的扩展学习。

正确性（所有合数都会被标记）证明

设一合数 (C)（要筛掉）的最小质因数是 (p_1)，令 (B = C / p_1)（(C = B × p_1)），则 (B) 的最小质因数不小于 (p_1)（否则 (C) 也有这个更小因子）。那么当外层枚举到 (i = B) 时，我们将会从小到大枚举各个质数；因为 (i = B) 的最小质因数不小于 (p_1)，所以 (i) 在质数枚举至 (p_1) 之前一定不会break，这回，(C) 一定会被 (B × p_i) 删去。

核心：亲爱的 (B) 的最小质因数必不小于 (p_1)。

例：(315 = 3 × 3 × 5 × 7)，其最小质因数是 (3)。考虑 (i = 315 / 3 = 105) 时，我们从小到大逐个枚举质数，正是因为 (i) 的最小质因数也不会小于 (3)（本例中就是 (3)），所以当枚举 (j = 1 (Prime[j] = 2)) 时，(i) 不包含 (2) 这个因子，也就不会break，直到 (Prime[j] = 3) 之后才退出。

当然质数不能表示成“大于1的某数×质数”，所以整个流程中不会标记。

线性复杂度证明

注意这个算法一直使用“某数×质数”去筛合数，又已经证明一个合数一定会被它的最小质因数 (p_1) 筛掉，所以我们唯一要担心的就是同一个合数是否会被“另外某数 × (p_1) 以外的质数”再筛一次导致浪费时间。设要筛的合数是 (C)，设这么一个作孽的质数为 (p_x)，再令 (A = C / p_x)，则 (A) 中一定有 (p_1) 这个因子。当外层枚举到 (i = A)，它想要再筛一次 (C)，却在枚举 (Prime[j] = p_1) 时，因为 (i mod Prime[j] == 0) 就退出了。因而 (C) 除了 (p_1) 以外的质因数都不能筛它。

核心：罪恶的 (A) 中必有 (p_1) 这个因子。

例：(315 = 3 × 3 × 5 × 7)。首先，虽然看上去有两个 (3)，但我们筛数的唯一一句话就是

			isPrime[ i*Prime[j] ] = 0;

所以，(315) 只可能用 (105 × 3) 或 (63 × 5) 或 (45 × 7) 这三次筛而非四次。然后，非常抱歉，后两个 (i = 63, i = 45) 都因为贪婪地要求对应的质数 (Prime[j]) 为 (5) 、(7)，而自己被迫拥有 (3) 这个因数，因此他们内部根本枚举不到 (5) 、(7)，而是枚举到 (3) 就break了。

以上两个一证，也就无可多说了。

更新日志：

2019-02-22 原理简化；用词修改或订正。

2019-04-02 一些用词更准确；加入更多括号内的注释，减少回看上文的需要。