如何用这个质数生成器程序避免SPOJ上的TLE？

Question

这是SPOJ上的质数生成器程序。我面临着可怕的 "Time Limit Exceeded "错误。我怎样才能克服这个错误？以下是问题的链接https:/www.spoj.comproblemsPRIME1

会是什么原因呢？我还是个初学者，我在网上搜索了一下，它让我用一些算法，但现在我什么算法都不会。

#include <stdio.h>

void prime(int a,int b)
{
    int y=0;
    for (int i=a;i<=b;i++)
    {
        for (int j=2;j<i;j++)
        {
            int x=i%j;
            if (x==0)
            {
                break;
            }
            else
            {
                y++;
            }
        }
        if (y==i-2)
        {
            printf("%d\n",i);
        }
        y=0;
    }
}

int main()
{
    int test;
    int arr1[11],arr2[11];
    char space[11];
    scanf("%d",&test);

    if (test>10)
    {
        goto end;
    }

    for (int i=0;i<test;i++)
    {
        scanf("%d%c%d",&arr1[i],&space[i],&arr2[i]);
        if (arr1[i]>=1 && arr1[i]<=arr2[i] && arr2[i]<=1000000000 && arr2[i]-arr1[i]<=100000 && space[i]==' ')
        {
            prime(arr1[i],arr2[i]);
            printf("\n");
        }
    }
    printf("\n");
end:
    return 0;
}

Answer 1

下面是检查一个数字是否为质数的代码。它的复杂度是O(sqrt(N)).O(N*sqrt(N))提出的解决方案通过了所有的测试案例，因为n-m <=100000。

 bool checkprime(int x){
        if(x==1)
            return false;
        if(x<=3)
            return true;
        for(int i=2;i<=sqrt(x);i++){
            if(x%i==0)
                return false;
        }
        return true;
    }

一些伪代码来调用和检查一个数字是否是质数。

for(int i=l;i<=r;i++){
    if(checkprime(i))
        cout<<i<<endl;
    else
        continue;
 }

然而 埃拉托斯泰尼的分格筛子 方法的工作速度要快得多，是回答所有疑问的较好方法。

Answer 2

你的解法似乎是二次元的，对于大数会超时。为了提高效率，你可以尝试不同的方法，比如用 埃拉托斯泰尼之筛