关于欧拉筛(洛谷模板3383)

         欧拉筛是一种素数筛,避免了同一个数被多次筛除,可以在线性时间内找出指定范围内的素数。

        筛选素数,一种较为朴素的想法是,对于已经得到的素数集合中的元素,枚举其倍数并筛除。但是,在这个过程中,会有同一个合数被筛多次的可能,例如,由于15=3*5,所以它既会被3所筛除,又会被5所筛除。由此可以自然地想到一种优化途径:通过制定一种规则,使得每个合数都只被筛除一次。

        在这里,我们采用的方案是,让每一个合数都只被其最小的质因数筛除,也等价于让其只被最大的非自身因数筛除。

       代码及详细注释如下:

        

#include <stdio.h>
#include <stdlib.h>
int state[100000005];
int prime[100000005];
int main()
{

    int count=1,n,q,i,j,search;
    state[1]=1;//1表示非质数
    scanf("%d %d",&n,&q);
    //对于每一个合数,都可以将它写成最大非自身因数乘以最小质因数的形式
    for (i=2;i<=n;i++)//每一轮希望筛除以i为最大非自身因数的合数
    {
        if (state[i]==0)
        {
            prime[count++]=i;
            //若i为合数,则一定已经被某个小于i的i1给筛除掉
            //所以至今未被筛除的必为质数,加入质数表
        }
        //无论i是否为质数,都有资格作为最大非自身因数
        for (j=1;j<count && prime[j]*i<=n;j++)
        //枚举质数表,希望它成为与最大非自身因数对应的最小质因数
        {
            state[prime[j]*i]=1;//筛除操作
            if (i%prime[j]==0) break;
            //如果i以prime[j]为质因子,则继续向后枚举没有意义,理由如下:
            //设k>j,则prime[k]>prime[j],i*prime[k]将以i的质因子prime[j]为最小的质因数
            //也就是说,即使我现在不筛除掉i*prime[k],它也会被prime[j]乘以某个数所筛除
        }

    }
    for (i=1;i<=q;i++)
    {
        scanf("%d",&search);
        printf("%d\n",prime[search]);
    }

}

        

       

上一篇:[NCTF2019]babyRSA


下一篇:素数区间