愿您的未来不再有悲伤。——《对某飞行员的追忆》

素数筛

素数筛法，是一种快速“筛”出 ~ 之间的所有素数的方法，把这段范围内的正整数按从小到大排序，逐步筛掉非素数留下素数。

虽然我也不知道每个代表什么意思但是就是很有艺术感

朴素筛法

这是一种小朋友都可以想到的筛法，相信你也可以。

遍历 ~ ，对于每个在此范围内的整数 再遍历 ~ ，如果 ~ 中有数字可以整除 ，就说明 不是素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cnt = 0, pr[N];
for (int i = 2; i <= n; i ++)
{
	k = true; // 标记为素数 
	for (int j = 2; j <= n - 1; j ++)
	{
		if (i % j == 0)
		{
			k = false;
			break;
		}
	}
	if (k == true)
		pr[++ cnt] = i;
}

其实我们不用全部遍历，因为如果 是 的除它之外最大的因子，那么 ，如果前面没有，后面就不用扫了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int cnt = 0, pr[N], m;
for (int i = 2; i <= n; i ++)
{
	k = true; // 标记为素数
	for (int j = 2; j * j <= n; j ++)
	{
		if (i % j == 0)
		{
			k = false;
			break;
		}
	}
	if (k == true)
		pr[++ cnt] = i;
}

现在的时间复杂度是 ，非常糟糕，那么肯定会有人不能接受，然后大呼：“我不能接受！”。

所以我们有了接下来的素数筛法，正是因为这些发现它们的数学家不能接受这样糟糕的复杂度。

埃拉托色尼筛

这是一种比小朋友大一点的中朋友都可以想到的筛法，相信你也可以。

我们把 的数按顺序写出来：

从前往后看，找到第一个未被划掉的数 ，这说明它是质数。然后把 的倍数（不包括 ）划掉：

下一个未被划掉的数是 ，它是质数把 的倍数划掉：

接下来是 ，但是 已经超过 了，所以遍历结束，剩下未被划掉的都是素数。

这个过程写成代码就是：

1
2
3
4
5
6
7
8
bool isnp[N];
void Sieve (int n)
{
	for (int i = 2; i * i <= n; i ++)
		if (!isnp[i]) // 未被划去
			for (int j = i * i; j <= n; j += i) // 因为之前的肯定都被较小数划掉了，所以直接从 i * i 开始 
				isnp[j] = 1; // 标记为不是素数 
}

代码很简单，时间复杂度是 ，但是我们发现在筛的过程中我们会重复筛到同一个树，例如 会被 和 筛到 同时被 ， 和 筛到，数学家们认为这太糟糕了（难道你不这么认为吗？），所以我们要引入欧拉筛。

欧拉筛

这是一种比中朋友大一点的大朋友都可以想到的筛法，相信你也可以。

欧拉筛，又叫线性筛，其核心思想是每个合数都被其最小质因数筛掉。

这次我们需要维护一个质数表：

还是从头到尾遍历，第一个数是 ，未被划掉，把它放进质数表：

然后我们用 去乘质数表里的每一个数，划掉它们：

下一个是 ，加入质数表，划掉 和 ：

下一个是 （注意这里划掉的数也要遍历，只是不加入质数表），先划掉 ，但我们不划掉 ，因为 应该由它的最小质因数 筛掉，而不是 ：

实际上，对于 ，我们遍历到质数表中的 ，且发现 （ 整除 ）时，就应当停止遍历质数表。因为，设 （ 本身是 的最小质因数），那么对于任意 ，有 ，所以 的最小质因数不是 ，我们不应在此划掉它。

具体来说，如果这里的 能整除 ，则 ，那么对于任何大于 的质数 ，都有 ，其中 是一个比 要小的质数，所以 应该被 筛掉而不是被 筛掉。

下一个是 ，加入质数表，划掉 和 ：

请注意，此时 最小的质因数是 ，但是要求是此时 在质数表里，因为 前面没有 的最小质因数，然后 乘上 等于 ，我们就可以划掉 了。

下一个是 ，划去 ：

……按照这样下去，我们就可以筛掉所有的合数，得到一份质数表。

我们可以保证每个合数都被筛过，设任意合数 ，其中 是 的最小质因数。在处理 时，要遍历质数表，直到遇到 才结束，所以任意小于等于 的质数与 的乘积，都会在此时被筛掉。

而由于 （因为 的最小质因数是 ），所以在处理 时， 一定会被筛掉。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isnp[N];
vector<int> primes;
void Eular_Sieve (int n)
{
	for (int i = 2; i <= n; i ++)
	{
		if (!isnp[i])
			primes.push_back (i);
		for (int p : primes)
		{
			if (p * i > n)
				break;
			isnp[p * i] = 1;
			if (i % p == 0)
				break;
		}
	}
}

当然也可以改一种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Eular_Sieve (int n)
{
	for (int i = 2; i <= n; i ++)
	{
		if (!isnp[i]) 
			primes[++ cnt] = i, sum ++;
		for (int j = 1; j <= sum && j * primes[j] <= n; j ++)
		{
			isnp[primes[j] * i] = true;
			if (i % primes[j] == 0) 
				break;
		}	 
	}
}