素数的判断方法总结

目录

素数介绍

试除法

埃氏筛

欧拉筛

素数介绍

判断一个数n是不是素数：当时，用试除法；当时，试除法不够用，需要用高级算法。

试除法

把内的所有数去试除n，如果都不能整除，就是素数。

bool is_prime(long long n){
	iff(n<=1){
		return false;
	}
	for(long long i=2;i*i<=n;i++){
		if(n%i==0){
			return false;
		}
	}
	return true;
}

埃氏筛

埃氏筛主要是将质数的倍数进行一连串的筛出去，因为质数的倍数一定不是质数。 

int prime[N],cnt;
bool bprime[N];
void getPrime(int n){
	memset(bprime,false,sizeof(bprime));
	bprime[0]=true;
	bprime[1]=true;
	for(int i=2;i<=n;i++){
		if(!bprime[i]){
			prime[++cnt]=i;
			for(ll j=i*2;j<=n;j+=i){
				bprime[i]=true;
			}
		}
	}
}

埃氏筛中会出现数字重复计算的问题，可以使用欧拉筛解决。

欧拉筛

int prime[N],cnt;
bool bprime[N];
void getPrime(int n){
	memset(bprime,false,sizeof(bprime));
	for(int i=2;i<=n;i++){
		if(!bprime[i]){
			prime[++cnt]=i;
		}
		for(int j=0;j<cnt&&i*prime[j]<n;j++){
			bprime[i*prime[j]]=true;
			if(i%prime[j]==0){//避免了重复计算某些数字
				break;
			}
		}
	}
}