介绍

Eratosthenes筛法，又名埃氏筛法，对于求1~n区间内的素数，时间复杂度为n log n，对于10^6^ 以内的数比较合适，再超出此范围的就不建议用该方法了。
筛法的思想特别简单： 对于不超过n的每个非负整数p， 删除2p, 3p, 4p,…， 当处理完所
有数之后， 还没有被删除的就是素数。

代码

void init()
{
    int cnt=0;
    for(int i=0;i <= Max;i++)
        is_prime[i] = true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=Max;i++)
        if(is_prime[i])
        {
            prime[cnt++]=i;     //边筛边记录素数
            for(int j=2*i;j<=Max;j+=i)
                is_prime[j]=false;
        }
}

版权声明：本文为KeepZ原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/KeepZ/p/11343202.html