c++ - 你能告诉我为什么这会产生超过 spoj(质数生成器)的时间限制吗

Question

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;    

bool prime[1000000500];
void generate(long long end)
{
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;

        for(long long i=0;i<=sqrt(end);i++)
        {
         if(prime[i]==true)
         {
             for(long long y=i*i;y<=end;y+=i)
             {
                 prime[y]=false;
             }
         }
        }
}

int main()
{
    int n;
    long long b,e;
    scanf("%d",&n);
    while(n--)
    {
        cin>>b>>e;
        generate(e);
        for(int i=b;i<e;i++)
        {
            if(prime[i])
                printf("%d\n",i);
        }
    }
    return 0;
}

这是我的 spoj 素数生成器代码。
Altought 它生成与另一个接受的代码相同的输出..

Answer 1

您不需要筛选每个数字直到最后一个数字。那太傻了。只对开始和结束数字之间的范围进行操作。 (偏筛)

我已经用 Python 解决了这个问题，这就是我最终设法解决的方法。我还开始计算所有素数，直到最大潜在最大值 1000000000 的平方根。这只有 31623，所以不会花很长时间。

从此列表中使用那些数字直到当前案例最大值的平方根来筛选当前案例。