欧氏筛法

筛法——求n以内质数个数

int prime[Max];

bool flag[Max];

int EulerSieve(int n)

{

    int p=0;

    for(int i=2; i<=n; i++)

    {

    //记录质因数i。

        if(flag[i]==0)

            prime[p++]=i;

    //筛掉i的倍数(无论i为质数还是合数)

        for(int j=0; j<p&&i*prime[j]<=n; j++)

        {

            flag[i*prime[j]]=1;

        //如果i%prime[j]为0，即 i的质因数为prime[i],也即 i的最小质因数为prime[i].

        //则其后 i的倍数为prime[j]的倍数。也就无须重复标记了。

            if(i%prime[j]==0)

                break;

        }

    }

    return p;

}

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/qq_30603195/article/details/86677762