[数据结构与算法]素数判断-----朴素判断、埃氏筛法、欧拉筛法

朴素判断

时间复杂度O(n²)

#include<bits/stdc++.h> //朴素判断的方法肯定会超时 
using namespace std;
const int N=1e3; 
bitset<N> prime; 
bool judge(int x){
	for(int i=2;i<=x/i;i++){//这里判断范围要写成小于等于b/i,防止溢出int 
		if(x%i==0)	return false;	
	} 
	return true;
}
int main()
{
	int n=N;
	int cnt=0;
	for(int i=2;i<=n;i++){
		if(judge(i))	cnt++;
	} 
	cout<<cnt<<endl;
    return 0;
}

埃氏筛法

时间复杂度为O(nlog(logn))

#include<bits/stdc++.h> 
using namespace std;
const int N=1e8; 
bitset<N> prime; 
int main()
{
	int b=1e7;
	prime[0]=1;
	prime[1]=1;
	int cnt=0;
	for(int i=2;i<=b/i;i++){//这里判断范围要写成小于等于b/i,防止溢出int 
		if(!prime[i]){
			for(int j=i*i;j<=b;j+=i){//注意初始为i*i，步长为i。这一步是为了把所有i的倍数都标记 
				prime[j]=1;
			}
		}
	} 
	for(int i=2;i<=b;i++)
	if(!prime[i])	cnt++;
	cout<<cnt<<endl;
    return 0;
}

欧拉筛法

时间复杂度为O(n)

这里欧拉筛法的优点是在计算过程中就把所有素数存在一个数组里了，速度也更快，但是占用的空间会更大。

#include<bits/stdc++.h> //这里欧拉筛法的优点是在计算过程中就把所有素数存在一个数组里了，速度也更快，但是占用的空间会更大。 
using namespace std;
const int N=1e7+5; 
bitset<N> prime;//标记下标数是否为素数 
int prime_s[N],p=0; //prime_s存放素数 
int main()
{
	int cnt=0;
	for(int i=2;i<=N;i++){
		if(!prime[i]){
			prime_s[++p]=i;
			cnt++;
		}
		for(int j=1;j<=p&&i*prime_s[j]<=N;j++){//这里条件j<=p可以删除，因为prime_s数组不可能满，总会遇到一个为0的数字，就break了 
			prime[prime_s[j]*i]=1;
			if(i%prime_s[j]==0)	break;
		}
	}
	cout<<cnt<<endl;
    return 0;
}