素数的两种筛法

介绍两种筛法

第一种：埃拉托斯特尼(Eratosthenes)筛法
简称：普通筛或埃氏筛

时间复杂度：O(nloglogn)

下面上普通筛法的两种写法及优化

写法1：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int a[N];
void ss(int n){
	memset(a,-1,sizeof(a));//a[i]=-1 先假定所有数都为素数,i是素数a[i]=-1,不是素数a[i]=0 
	a[0]=a[1]=0;
	for(int i=2;i<=n;i++)
		if(a[i])
		for(int j=i*2;j<=n;j+=i) a[j]=0; //从i*2,开始以他自身为倍数相加的数都是合数 
}
int main(){
	int n;
	while(cin>>n){
		ss(n); 
		for(int i=2;i<=n;i++)
			if(a[i]) cout<<i<<endl;
	}
} 

写法2：最后一个for循环可以改写一下
实质一样。

void ss(int n){
	memset(a,-1,sizeof(a));
	a[0]=a[1]=0;
	for(int i=2;i<=n;i++)
		if(a[i])
		for(int j=2;j*i<=n;j++) a[i*j]=0; 
}

两处优化，上代码。

void ss(int n){
	memset(a,-1,sizeof(a));
	a[0]=a[1]=0;
	for(int i=2;i<=sqrt(n);i++)//优化1:只需要到sqrt(n) 
		if(a[i])
		for(int j=i*i;j<=n;j+=i) a[j]=0; //j从i*i开始 
}

第二种：欧拉筛法。

时间复杂度：O(n)
原理与普通筛类似，只是避免了重复筛同一个合数
下面上代码

const int N=1e5;
bool a[N];
void Ess(int n){
	 memset(a,true,sizeof(a));
	 int p[N],cnt=0;
	 for(int i=2;i<=n;i++)
	 {
	 	if(a[i]) p[cnt++]=i;
	 	for(int j=0;j<cnt&&i*p[j]<=n;j++)//每个合数只用其最小质因数去筛 
	 	{
	 		a[i*p[j]]=false;
	 		if(i%p[j]==0) break; 
		}//如果i能被p[j]整除,说明i*p[j+1]已经被筛过,因为i是p[j]的倍数,所以i*[p+1]是p[j]的倍数 
	 } 
} 

注意以上两种筛法1都要特判,
如果题目给的范围还有需要将1特判

----定理-----：任意大于1的整数的最小因数是素数。
而且对合数进行筛选时，它的所有因数一定都被筛过了。

看完以上两种素数筛法：去洛谷练练手，
题目传送门：模板题