1 试除法判断素数
bool isPrim(int n){
if(n<=1)return false;
for(int i=2;i*i<=n;i++){
if(n%i==0) return false;
}
return true;
}
2 埃式筛法求素数的个数;
const int MaxN =1e7;
int a[MaxN+1];//存储素数
bool vis[MaxN+1];//标志筛选过的数
int E_search(int n){
int k=0;
for(int i=0;i<=n;i++)vis[i]=false;
for(int i=2;i*i<=n;i++)
{
if(!vis[i]){
a[k++]=i;
for(int j=i*i;j<=n;j=j+i)
vis[j]=true;//i的倍数全部筛除
}
}
return k; //素数个数
}
评论