素数筛法：从埃氏筛到欧拉筛

前言

素数又称质数，是指一个大于 $1$ 的正整数，如果除了 $1$ 和它本身以外，没有其他的约数，例如 $2,3,5,7,3021377$ 等，反之就是合数。 $1$ 既不是素数也不是合数。

素数就像整数世界里的原子，整个整数世界都是由这些素数原子组成的，比如 $15=3\times 5$ ， $121=11\times 11$ 等等。有关素数的问题是数论研究的主要课题，我国著名数学家华罗庚教授及陈景润、王元研究员、潘承洞教授等对数论的研究都有重要贡献.

早在 2000 多年前的古希腊，伟大的数学家欧几里德就用反证法证明了：素数有无穷多个。在他的不朽名著《几何原本》第四卷命题 20 中是这样叙述的：预先给定几个素数，则有比他们更多的素数。他是这样证明的：设 $a,b,c$ 是给定的素数，构造一个新的数 $t=a\times b\times c+1$ ，则已有的素数 $a,b,c$ 均不能整除 $t$ ，所以要么 $t$ 本身就是素数，此时 $t$ 不等于 $a,b,c$ 中任意一个数；要么 $t$ 能被不同于 $a,b,c$ 的某一个素数整除，因此必然存在一个素数不同于已有的素数 $a,b,c$ 。例如： $2\times 3\times 5+1=31,3\times 5\times 7+1=106=2\times 53$ 。也就是说，有了 $n$ 个素数，就可以构造出第 $n+1$ 个素数，因此素数有无穷多个。

埃式筛法

对于数据范围比较大的情况下，需要找出所有素数，可以采用“筛选法”求出“素数表”。具体方法如下：

先将 $2\sim N$ 之间的所有数写在纸上： $2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40\cdots$
在 $2$ 的上面画一个圆圈，然后划去 $2$ 的其他倍数；
第一个既未画圈又没有被划去的数是 $3$ ，将它画圈，再划去 $3$ 的其他倍数；
现在既未画圈又没有被划去的第一个数是 $5$ ，将它画圈，并划去 $5$ 的其他倍数……
依次类推，一直到所有小于或等于 $N$ 的各数都画了圈或划去为止。这时，表中画了圈的以及未划去的那些数正好就是不超过 $N$ 的素数。实现代码如下：

//埃式筛法
#include <bits/stdc++.h>
using namespace std;

bool isprime[10000000];

void sieve(int n)
{
	memset(isprime,true,sizeof(isprime));
	for(int i=2;i*i<=n;i++)
	{
		if(isprime[i])
		{
			for(int j=i*i;j<=n;j+=i)
				if(isprime[j])
					isprime[j]=false;
		}
	}
} 

int main()
{
	int n;
	scanf("%d",&n);
	sieve(n);
	for(int i=2;i<=n;i++)
		if(isprime[i])
			printf("%d ",i);
	return 0;
}

欧拉筛法

仔细分析上述代码发现，这种方法会造成重复筛除合数，影响效率。比如 $30$ ，在 $i=2$ 的时候， $k=2\times 15$ 筛了一次；在 $i=5,k=5\times 6$ 的时候又筛了一次。所以，也就有了“快速线性筛法”。快速线性筛法没有冗余，不会重复筛除一个数，所以“几乎”是线性的，虽然从代码上分析，时间复杂度并不是 O(n) 。先看实现代码：

//欧拉筛法
#include <bits/stdc++.h>
using namespace std;

bool isprime[10000000];
int prime[5000000];

void Euler_sieve(int n)
{
	memset(isprime,true,sizeof(isprime));
	prime[0]=0;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i])
			prime[++prime[0]]=i;
		for(int j=1;j<=prime[0] && i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0)
				break;
		}
	}
} 

int main()
{
	int n;
	scanf("%d",&n);
	Euler_sieve(n);
	for(int i=1;i<=prime[0];i++)
		printf("%d ",prime[i]);
	return 0;
}

首先，先明确一个条件，任何合数都能表示成一系列素数的积。

如果 $i$ 是素数的话，那简单，一个大的素数 $i$ 乘以不大于 $i$ 的素数，这样筛除的数跟之前的是不会重复的。筛出的数都是 $n=p_1\times p_2$ 的形式， $p_1$ 和 $p_2$ 不相等；
如果 $i$ 是合数，此时 $i$ 可以表示成递增素数相乘 $i=p_1\times p_2\times \cdots \times p_n$ ， $p_i$ 都是素数 $(2\leq i\leq n),p_i\leq p_j(i\leq j)$ ， $p_1$ 是最小的系数。

根据上述代码，当 $p_1==\text{prime}[j]$ 的时候，筛除就终止了，也就是说，只能筛出不大于 $p_1$ 的质数 $\times i$ 。

我们可以直观地举个例子。 $i=2\times 3\times 5$ ，此时能筛除 $2\times i$ ，不能筛除 $3\times i$ ，如果能筛除 $3\times i$ 的话，当 $i'=3\times 3\times 5$ 时，筛除 $2\times i'$ 就和前面重复了。

当然，还有 2 个结论是可以证明的：

一个数不会被重复筛除；
合数肯定会被筛除。

参考资料：

林厚从《信息学奥赛之数学一本通》

前言

埃式筛法

欧拉筛法

继续读