c - 我在 C 程序中不断收到错误 "Time Limit Exceeded"。我应该如何提高我的代码效率？

Question

已关闭。这个问题是 not reproducible or was caused by typos 。目前不接受答案。

---

这个问题是由拼写错误或无法再重现的问题引起的。虽然类似的问题可能是 on-topic在这里，这个问题的解决方式不太可能帮助 future 的读者。

已关闭 7 年前。

Improve this question

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers! The input begins with the number t of test cases in a single line (t <= 10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n - m<=100000) separated by a space.

我不知道如何用高级概念来解决这个问题，所以我只使用循环来解决它。

本题时限为6.00s

#include <stdio.h>
int main(void)
{
    int a[1],b[1],j,i,test,k,flag;
    scanf("%d",&test);
    for(i=1;i<=test;i++)
    {
        for(k=0;k<1;k++)
        {
            scanf("%d %d",&a[k],&b[k]);
        }
        for(j=a[0];j<=b[0];++j)
        {
            flag=0;
            for(k=2;k<j;++k)
            {
                if(j%k==0)
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0)
            {
                printf("\n%d",j);
            }
        }
    }
    return 0;
}

Answer 1

一些可以提高性能的建议。

1. 您无需一直检查到 b[0]。您只需检查 sqrt(b[0]) 以内。

2. 更新循环，以便仅检查奇数而不是所有数字。

替换

for(j=a[0];j<=b[0];++j)
{

由

int stop = sqrt(b[0]);
// Start with an odd number and keep incrementing j by 2 to keep it that way
for(j= (a[0]/2)*2+1; j <= stop; j +=2 )
{