引子：Question:

给定两个数min,max,求出[min,max]区间的所有素数

C++的区间质数筛选，有两种方法。

Eratosthenes Algorithm

第一种就是Eratosthenes算法，该算法基于一个思想：对于任意的整数x，2x,3x,4x....一定不是质数。那好以二为起始点，很容易写出一下代码：

Code(Eratosthenes-1)

#include<cstdio>
#include<cstring>
bool vis[32768];
int main(){
	int min,max;
	scanf("%d %d",&min,&max);
	memset(vis,1,sizeof(vis));
	vis[1]=0,vis[0]=0;
	for(int i=2;i<=max;i++){
		if(vis[i]){
			if(i>=min){
				printf("%d ",i);
			}
		}
		for(int j=i;j<=max;j+=i){
			vis[j]=0;
		}
	}
	return 0;
}

我再给一张图，来解释它的运算过程：

 我们会发现j可以从i*i开始也不会影响结果。观察发现比i*i小的数在之前能够保证已经筛去了。这样可以减少不必要的冗余计算（重复标记）

Code(Eratosthenes-2)

#include<cstdio>
#include<cstring>
bool vis[32768];
int main(){
	int min,max;
	scanf("%d %d",&min,&max);
	memset(vis,1,sizeof(vis));
	vis[1]=0,vis[0]=0;
	for(int i=2;i<=max;i++){
		if(vis[i]){
			if(i>=min){
				printf("%d ",i);
			}
		}
		for(int j=i*i;j<=max;j+=i){
			vis[j]=0;
		}
	}
	return 0;
}

时间复杂度：O（N log log N）

但即使这样，也无法避免重复计算！

如12被标记了两次，3*4与2*6。所以说，避免冗余运算是提高算法运算效率的关键，那么有没有这样一种完美的算法呢？有，那就是线性筛法！

线性筛法 Algorithm

先上代码：

Code(线性筛法)

#include<cstdio> 
#include<cstring>
int vis[32768];
int prime[32768];
int main(){
	int min,max;
	scanf("%d %d",&min,&max);
	memset(vis,0,sizeof(vis));
	int tot=0;
    for(int i=2;i<=max;i++){
    	if(vis[i]==0){
    		prime[++tot]=i;
    		vis[i]=i;
		}
		for(int x=1;x<=tot;x++){
			if(prime[x]*i>max || prime[x]>vis[i])break;
			vis[prime[x]*i]=prime[x];
		}
	}
	for(int i=1;i<=tot;i++){
		if(prime[i]>=min){
			printf("%d ",prime[i]);
		}
	}
	return 0;
}

 我们从本质上思考重复计算的原因，发现我们对于同一个数的计算方式不同。那么怎样才能确定一个唯一的计算方式呢？关键是找质因子，因为每一个大于1的正整数都能分解为若干个质数的乘积。给一张图启迪你一下：

这样时间复杂度降到了O(N)

 撒花，完结。。。

 End~~~

谢谢支持，欢迎评论留言。