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

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

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

先上代码：

#include
#include
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< 
说明：
 为什么j可以从i * i开始，而不是从i+i开始，是因为通过找规律可以知道，在i>2时， i*(i-1)的数已经被筛完了，所以从i * i开始筛。
 缺点：
 埃氏筛的缺点很明显，例如12=26 =34，他奖会被筛多遍。这个时候欧拉筛就孕育而生，寻找最小质因子，每个合数只被最小质因子筛。
 
欧拉筛-euler 
代码：
 
#include
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%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时会计算。因为欧拉筛法的原理便是通过最小素因子来消除
 
完结！
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710505.html