数论基础3 ---素数

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; //素数个数 

}