素数

素数的判断

不能被[2，sqrt（n）]内的所有整数整除

埃式筛法求素数

//埃式筛法-求[2,n]上有多少个素数，有哪些素数 
#include<bits/stdc++.h>
using namespace std;
const int N=1e8;
bool a[N+5];	//筛掉为true,空间复杂度O(n)
//埃式筛法 -求[2,n]上有多少个素数
void Era_prime(int n){
	memset(a,false,sizeof(a));
	for(int i=2;i<=sqrt(n);i++){
		if(a[i]) continue;
		for(int j=i*i;j<=n;j+=i){
			a[j]=true;
		}
	}
} 
int main(){
	int n;
	Era_prime(N);//埃式筛法求出N以内的所有素数 
	while(cin>>n){
		int ans=0;
		for(int i=2;i<=n;i++){
			if(!a[i]){
//				cout<<i<<" ";
				ans++;
			}
		}
		cout<<ans<<endl;
		cout<<"math:"<<n/log(n)<<endl;
	}
	return 0;
}