求解n以内的素数之埃拉特斯特尼筛和欧拉筛

一时失言乱红尘 2021-12-09 17:34 319阅读 0赞

## 首先我像声明一点：我的博客只有干货！！！！！ ##

1.  埃筛  
    埃筛就是在判断出来一个数是素数之后那么他的倍数全部都是合数  
    缺点就是我们可能对同一个数有重复筛选的过程  
    时间复杂度O(nloglogn)

#include<bits/stdc++.h>
    using namespace std;
    const int N=1000000;//定义常量的时候不要忘记了加=
    bool book[N+1];//标记变量
    void op(int n){
    	book[1]=1;
    	for(int i=2;i<=n;++i){//n以内的数我们进行i筛
    		if(book[i]==0){
    			for(int j=i+i;j<=n;j+=i){//如果是倍数的话那我们就对其进行标记
    				book[j]=1;
    			}
    		}
    	}
    }
    int main(){
    	int n;
    	cin>>n;
    	op(n);
    	for(int i=2;i<=n;++i){
    		if(!book[i])cout<<i<<" ";//输出
    	}
    	return 0;
    }

欧拉筛：  
欧拉筛是枚举素数表中的数据来进行判重  
因为每个合数都可以表示成为一个最小质数乘以合数的形式所以在代码中加上的最后一条if语句就能够避免重判的现象

#include<bits/stdc++.h>
    using namespace std;
    const int N=1000000;
    int prime[N+1];
    bool book[N+1];
    int op(int n){
    	int cnt=0;
    	for(int i=2;i<=n;++i){
    		if(book[i]==0){
    			prime[cnt++]=i;
    		}
    		for(int j=0;j<cnt&&i*prime[j]<=n;++j){
    				book[i*prime[j]]=1;
    				if(i%prime[j]==0)break;//这一步就是避免判重的
    		}		
    	}
    	return cnt;
    }
    int main(){
    	int n;
    	cin>>n;
    	int cnt=op(n);
    	for(int i=0;i<cnt;++i){
    		cout<<prime[i]<<" ";
    	}
    	return 0;
    }

**对比：**  
埃筛函数需要一个数组用来记录bool，下标就是数值，而且没有返回值  
欧拉筛有int返回值，因为最后要对素数表进行遍历，而且需要开辟两个数组，一个用来bool，一个用来存素数  
\*\*注解：\*[\*欧拉筛去重证明：][Link 1]

[Link 1]: https://www.jianshu.com/p/2031036dba4b