埃氏筛

当我们遇到一些情况，需要筛选出素数，但是用for循环又太耗时，那可以用埃氏筛把一定量的素数给筛选出来。

代码如下：

int tot,maxn=1000,pri[maxn];
bool is[maxn];
void Eratosthenes()
{
    tot=0;
    memset(is,1,sizeof(is));//定义is数组中所有数都为1；即假设所有数都为素数，方便后面筛出素数
    is[0]=is[1]=0;//数字0和1的素数都为0
    for(int i=2;i<maxn;i++)
    {
        if(is[i])//如果是素数的话，is[]肯定为1
        {
            pri[++tot]=i;//将素数存入pri数组中
            for(int j=i+i;i<maxn;j+=i)//筛出不是素数的数
            {
                is[j]=0;
            }
        }
    }
}