【算法专题】筛质数

筛质数的三种方法

什么是质数？
只能够被 1 和它本身整除的数叫做质数

1、朴素筛法

那么我们从定义出发，假设我们要判断 \(n\) 是否是质数，我们从 \(1\) 开始枚举每一个数，一直到 \(n\) 看看有没有其他的数能够被 \(n\) 整除，如果没有，那么 \(n\) 就是质数。

假设我们要筛出从 \(1\) ~ \(n\) 之间的质数，那么时间复杂度为 \(O(n\sqrt n)\)。

int primes[N], cnt;

bool is_primes(int x)
{
	for (int i = 2; i <= sqrt(x); i++) // 小优化，可以枚举到 根号n
		if (x % i == 0)
			return false;
	return true;
}

void init(int n) // 筛质数
{
	for (int i = 2; i <= n; i++)
		if (is_primes(i))
			primes[cnt++] = i;
}

那么我们可不可以想到，质数的倍数是不是一定不是质数了，那么我们可以进行一次优化。

int primes[N], cnt;
bool st[N]; // 标记是否是被筛过了

void init(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i]) primes[cnt++] = i; // 把质数存起来
		for (int j = i + i; j <= n; j += i) // 不管i是不是质数，枚举i的倍数，筛掉
			st[j] = true;
	}
}

这样时间复杂度就变成了 \(O(n\log n)\)

2、埃氏筛（埃拉托斯特尼筛法）

我们知道，朴素筛法就是一直枚举，把它枚举到的所有的数的倍数都筛掉，那么我们想想可不可能合数不用枚举它的倍数呢，因为质数的倍数一定可以表示成某个合数，所以我们可以只把质数的倍数给筛掉。

埃氏筛就是从另一个角度来看，把所有质数的倍数给筛掉。

这样时间复杂度就变成了 \(O(n \log \log n)\)

int primes[N], cnt;
bool st[N]; // 标记是否是被筛过了，没被筛过肯定是质数

void init(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i])
		{
			primes[cnt++] = i; // 把质数存起来
			for (int j = i + i; j <= n; j += i) // 枚举i的倍数，筛掉
				st[j] = true;
		}
	}
}

3、欧拉筛（线性筛）

我们使用埃氏筛后，时间复杂度变得很低了，但是依然不是线性的，说明还是可以有优化的空间，那么大家想一想埃氏筛的过程，我们是不是有重复的筛数的情况呀。

比如说遍历到 \(3\) ，那么是不是 \(15\) 是 \(3\) 的倍数，被筛掉一次，遍历到 \(5\) 的时候，\(15\) 也是 \(3\) 的倍数，是不是又要筛一次呀，所以我们进行了很多重复的操作。

那么欧拉筛就解决了这个问题，它加了一个优化，它也是筛质数的倍数，但是它加了一个判断条件，假如要筛的数是之前存下来的质数的倍数，那么我们就直接break，开始进行筛下一个数。

int primes[N], cnt;
bool st[N];

void init(int n)
{
	for (int i = 2; i <= n; i++)
	{
		if (!st[i]) primes[cnt++] = i;
		for (int j = 0; primes[j] <= n / i; j++)
		{
			st[i * primes[j]] = true; // 用质因子筛
			if (i % primes[j] == 0) break;
			// 当走到这里时，这个质因子是i能整除的最小的了，我们不用判断后面的质因子了
			// 如果不加优化，那么这个数就会被重复筛，我们举的例子。
		}
	}
}

那么我们可以清楚的看到，每个数都被筛了，并且只筛了一次，所以时间复杂度为 \(O(n)\)