part4：素数判别

2024-08-27 07:16:47

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

int pri[],n,num;

bool  yes[];

sieve(int a)//筛

{

    for(int i=;i<=a;i++)yes[i]=;

    for(int i=;i<=a;i++){

        if(yes[i]){

            pri[++num]=i;

            for(int j=i*;j<=a;j+=i)

            yes[j]=;}

        }

}

int main()

{

    cin>>n;

    sieve(n);

    for(int i=;i<=num;i++)

    cout<<pri[i]<<endl;

}//伪代码qwq

法三：线形筛：

int pri[],n,num;

bool  yes[];

int hs(int a){

    num=;

    memset(yes,,sizeof(yes));

    for(int i=;i<=a;i++){

        if(!yes[i])pri[num++]=i;

        for(int j=;j<=num&&i*pri[j]<=a;j++){

        yes[i*pri[j]]=;

        if(i%pri[j]==)break;

        }

    }

}

int main()

{

    cin>>n;

    hs(n);

    for(int i=;i<num;i++)

    cout<<pri[i]<<endl;

}

end-

最新文章

热门文章