数论基础3 ---素数

数论基础3 ---素数

leaf
2022-02-08 / 0 评论 / 7 阅读 / 正在检测是否收录...

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

}

0

评论

博主关闭了所有页面的评论