您的位置: 首页 > IT文章 > part4：素数判别

part4：素数判别

分类: IT文章 • 2024-01-20 15:01:42

法一：
√n判别
这个的话就是暴力了吧，不过只能判别单个数是不是质数，而且很大的话会爆
```
//没有代码qwq（不想写
```
法二：埃式筛法
O(nloglogn)判别
直接代码好不啦：

int pri[100000],n,num;
bool  yes[100010];
sieve(int a)//筛
{
    for(int i=1;i<=a;i++)yes[i]=1;
    for(int i=2;i<=a;i++){
        if(yes[i]){
            pri[++num]=i;
            for(int j=i*2;j<=a;j+=i)
            yes[j]=0;}
        }
}
int main() 
{
    cin>>n;
    sieve(n);
    for(int i=1;i<=num;i++)
    cout<<pri[i]<<endl;
}//伪代码qwq

法三：线形筛：

int pri[10000],n,num;
bool  yes[10010]; 
int hs(int a){
    num=0;
    memset(yes,0,sizeof(yes)); 
    for(int i=2;i<=a;i++){
        if(!yes[i])pri[num++]=i; 
        for(int j=0;j<=num&&i*pri[j]<=a;j++){
        yes[i*pri[j]]=1;
        if(i%pri[j]==0)break;
        }
    }
}
int main() 
{
    cin>>n;
    hs(n);
    for(int i=1;i<num;i++)
    cout<<pri[i]<<endl;
}

end-