我不断收到错误消息“超过了时间限制".在C程序中.如何提高代码效率? [英] I keep on getting the error "Time Limit Exceeded" in a C program.How should i make my code efficient?

问题描述

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

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.

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

I don't know how to solve the problem with advanced concepts so I solved it by using just loops.

此问题的时间限制为6.00s

The time limit to this problem is 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;
}

推荐答案

可改善性能的建议对.

1. 您无需一路检查到 b [0] .您最多只需要检查 sqrt(b [0]).

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

Update the loop so that you check only odd numbers not all numbers.

替换

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程序中.如何提高代码效率?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！