c - 我一直在C程序中遇到错误“超过时间限制”。如何提高代码效率？

Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？ Update the question，所以它是on-topic，用于堆栈溢出。
                        
                        4年前关闭。
                                                                                            
                
        

  彼得想为其密码系统生成一些质数。救救他！您的任务是生成两个给定数字之间的所有质数！输入以一行中的测试用例数t（t <= 10）开头。在接下来的每个t行中，有两个数字m和n（1 <= m <= n <= 1000000000, n - m<=100000），以空格分隔。


我不知道如何用高级概念解决问题，所以我只使用了循环就解决了。

该问题的时间限制是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;
}

最佳答案

几个将改善性能的建议。


您无需一直检查到b[0]。您最多只需要检查sqrt(b[0])。
更新循环，以便仅检查奇数而不检查所有数字。




更换

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 )
{

关于c - 我一直在C程序中遇到错误“超过时间限制”。如何提高代码效率？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34338396/