埃氏筛&欧拉筛~Biu~素数

本文主要是介绍埃氏筛&欧拉筛~Biu~素数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

两种方法筛素数

素数定义：大于0的数，除了1和他本身之外，没有其他数可以整除它。
最小的素数：2
合数定义：大于0的数，除了1和他本身外，还存在其他数可以整除它。
最小的合数：4

实际上合数和质数是相对立的。

埃氏筛：

先上代码：

#include<iostream>
#include<string.h>
using namespace std;
const int maxn=100;
int vis[maxn];
int main()
{
	memset(vis,1,sizeof(vis));//初始都设定为是素数
	vis[0]=vis[1]=0;//0 1 不是素数
	for(int i=2;i<=maxn;i++){
		if(vis[i]){
			for(int j=i*i;j<=maxn;j+=i){//这里为什么可以从i*i开始呢？后文有说明
				vis[j]=0;//所有是i的倍数的数都是合数，即不是素数
			}
		}
	}
	for(int i=0;i<=maxn;i++){
		if(vis[i]) cout<<i<<" ";
	}
	return 0;
}

说明：
为什么j可以从ii开始，而不是从i+i开始，是因为通过找规律可以知道，在i>2时， i(i-1)的数已经被筛完了，所以从i * i开始筛。
缺点：
埃氏筛的缺点很明显，例如12=26 =34，他奖会被筛多遍。这个时候欧拉筛就孕育而生，寻找最小质因子，每个合数只被最小质因子筛。

欧拉筛-euler

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int vis[maxn],prime[maxn];

int main()
{
	memset(vis,1,sizeof(vis));
	memset(prime,0,sizeof(prime));
	vis[0]=vis[1]=0;
	for(int i=2;i<=maxn;i++){
		if(vis[i]){
			prime[0]++;//相当于一个记录素数的计数器
			prime[prime[0]]=i;//第i个数为prime
		}
		for(int j=1;j<=prime[0]&&i*prime[j]<=maxn;j++){//只遍历素数表，也就满足了用最小素数筛的需求。
			vis[i*prime[j]]=0;
			if(i%prime[j]==0) break;//为什么这里需要break;思考一下
		}
	}
    for(int i=0;i<=maxn;i++){
        if(vis[i]) cout<<i<<" ";
    }
	return 0;
}

说明：
对于 i%prime[j] == 0 就break的解释 ：当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。
举个例子 ：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除

完结！

这篇关于埃氏筛&欧拉筛~Biu~素数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！