Java教程

埃氏筛&欧拉筛~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~素数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!