how to reduce time taken by following program....getting tle error

general
, ,
1

#include<stdio.h>
#include<math.h>
void check(int num)
{
int i,flag;
if(num==2)
{
printf(“2\n”);
}
for(i=2;i<=((int)(sqrt(num))+1);i++)
{
if(num==1);
else if(num%i==0)
{
flag=1;
break;
}
else
{
flag=0;
}
}
if(flag==0)
{
printf("%d\n",num);
}
}
int main()
{
int a[10],b[10],n,j,i,k;
scanf("%d",&n); //no. of test
for(i=0;i<n;++i)
{
scanf("%d %d",&a[i],&b[i]);
}
for(k=0;k<n;k++)
{for(j=a[k];j<=b[k];j++)
{
check(j);
}
}

return 0;
}
2

Can you give the link to the question?

3

well i think u are just considering the provided testcases only.
the value of n might be very high and you are only storing the values in array of size 10 it should produce runtime error i think.
even if its running then tle might be because of the second loop

for(k=0;k<n;k++)
{for(j=a[k];j<=b[k];j++)
{
check(j);
}
}

try to think differently and reduce the iteration of this loop.

and about what you are doing with array see this might help you

1 Like
4

I suppose you want to find all primes numbers between two integers a and b. Before solving a problem you should find the time complexity required to solve the problem. You can have a look at these posts [link1][1] and [link2][2]. Complexity of your code is O(t*(b-a)*sqrt(MAX)) where MAX is the maximum value of number b and t is the no of test cases. This complexity will not pass. For solving problems on primes you can use [Sieve of Erastosthenes][3]. Normally sieve is applied on range [0,N] but since N can be very large, in this case you have to apply it on the range [a,b] for each test case. You just have to map 0 to a and n to b in the implementation of sieve. Have a look at my


[4]. Hope that helps :)

------
EDIT: You can answer each test case as you read it as i have done in my code. There is no need to store each test case in an array.

  [1]: http://discuss.codechef.com/questions/19987/number-of-instructions-that-can-be-acceptable-in-1-second
  [2]: http://discuss.codechef.com/questions/21718/not-getting-it-how-to-start-where-to-learn-plz-help?page=1#21734
  [3]: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
  [4]: http://ideone.com/l2WvAU
1 Like
5