素数的筛选——线性（欧拉）筛法_线性筛法求素数

        要筛选出以内的素数，一般有两种方法，一个是埃氏筛法，另一个是欧拉筛法。埃氏筛法就是从开始每次去除素数的倍数，在完成了一次去除后剩下的最小的数字就是一个素数，又可以从它开始去除它的倍数的数字了，这样一直到（是素数或者是被去除的数）为止。因为某个数总是素数的乘积，所以合数都会被去除。C++代码可以这样写：

//埃氏筛法 
bool *primes(int n){
	bool *p=(bool *)malloc(sizeof(bool)*(n+1));
	memset(p,true,n+1);
	p[0]=p[1]=false;
	for(int i=2;i<=n;){
		int j=i*i;
		while(j<=n){
			p[j]=false;
			j+=i;
		}
		while(!p[++i]);
	}
	return p; 
}

不过这种算法时间复杂度为，欧拉筛法的时间复杂度为 线性阶的，因而它又被称为线性筛法。

线性筛法的大致过程可以描述如下：

1. 将标记为素数并取
2. 将标记为合数，其中：1）若i是合数，则，是的最小质因数；2)若是质数，
3. ，并跳转至第2步。

 通过欧拉筛法，可以去掉合数，筛选出质数，这是因为：

（1）对于一个合数，若，而和为小于的质数，则一定被去掉。否则，则有，是是的最小质因数，取的最小质因数成立，。

（2）在上述筛法中，对于，若存在使，则有，又，

矛盾，因此不存在这样的，所以已被去除。

而线性筛法，大致可以用如下的C++代码描述：

#include<iostream>
using namespace std;
const int N=100000010;//我的机器上int为4个字节 
int vis[N];
int prim[N];
int cnt;
 
void get_prim(int n){
	for(int i=2;i<=n;i++){
		if(!vis[i])prim[++cnt]=i;
		for(int j=1;1ll*i*prim[j]<=n;j++){
			vis[i*prim[j]]=1;
			if(i%prim[j]==0)break;
		}
	}
}
 
int main(){
	int n;
	cin>>n;
	get_prim(n);
	for(int i=1;i<=cnt;i++){
		cout<<prim[i]<<" ";
	}
	return 0;
}