[算法]素数筛法(埃氏筛法&线性筛法)

一、素数筛的定义

给定一个整数n，求出[1,n]之间的所有质数(素数)，这样的问题为素数筛(素数的筛选问题)。

二、埃氏筛法(Eratosthenes筛法)

埃氏筛法又叫做Eratosthenes筛法，一般叫做埃氏筛。埃氏筛的思想是：
\(\forall x\in Z\)的倍数\(2x，3x，...\)都不是质数。
因此我们可以从2开始有小到大扫描每个数\(x\)，并把\(x\)的倍数\(2x，3x，4x，...\)标记为合数。当这个某个数\(y\)被扫描到的时候，如果\(y\)没有被标记为合数，那么\(y\)就属于质数。
Eratosthenes筛法的复杂度为\(O(NloglogN)\)。效率非常接近线性。
以下为Eratosthenes筛法模板：

inline int Eratosthenes(int n){
	for(int i=1;i<=n;i++) is_p[i]=1;
	memset(prime,0,sizeof(prime));
	is_p[1]=is_p[0]=0;
	for(int i=1;i<=n;i++){
		if(!is_p[i]) continue;
		prime[++tot]=i;//prime[]存储了[1,n]的所有质数
		for(int j=i*2;j<=n;j+=i) is_p[j]=0;//j为合数
	}
	return tot;
}

三、线性筛法

我们知道，一个算法的复杂度组成有一类是因为重复的计算。这就是埃氏筛的问题所在，埃氏筛会重复标记已标记的合数。例如12会被质数2重复标记，同时也会被3标记。如果我们仅能标记一次合数就好了。
线性筛法通过从大到小不断累乘质因子的方法标记合数，即12的标记方式为：\(12=6\times 2=(3\times2)\times2\)。
实现方式为：

1.依次扫描[2,n]的每一个数a
2.若没有被标记为合数，说明a是质数，此时保存起来
3.依次扫描\(a\times prime[x]\leqslant n\)的每一个质数，标记\(a\times prime[x]\)为合数，且保证prime[x]为\(a\times prime[x]\)的最小质因子。

因为每个合数只会被它的最小质因子筛一次，所以线性筛的复杂度为\(O(N)\)。
以下为线性筛法的模板：

int notp[N],prime[N];
inline int get_primes(int n){
	int tot=0;
	for(int i=2;i<=n;i++){
		if(!notp[i]) prime[++tot]=i;
		for(int j=1;j<=tot,i*prime[j]<=n;j++){
			notp[i*prime[j]]=1;//标记合数，此时prime[j]是合数i*prime[j]的最小素因子
			if(i%prime[j]==0) break;
			//一个小合数与大质数 可以被 一个大合数与小质数 替代
			//3*6=18，同样的，2*9=18。此时我们不如让2*9标记18 
		}
	}
	return tot;
}

四、一个性质

• 任何一个合数n必定包含一个不超过\(\sqrt n\)的质因子。