time limit exceeded problem

#include <stdlib.h>
#include <math.h>
int prime(int x)
{
int j,flag=1;
for(j=2;j<=sqrt(x);j++)
if(x%j==0) flag=0;
else flag=1;
return flag;
}
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
int m,n,i,j;
scanf("%d%d",&m,&n);
for(i=m;i<=n;i++)
if(prime(i)==1)
printf("%d\n",i);
printf("\n");
for(i=m+1;i<n;i++)
if(prime(i)==1)
printf("%d\n",i);
}
return 0;
}

Though your code is correct but this approach isn’t fast enough to pass the time limit set for the problem. You need some faster method to find prime numbers.

Sieve of Eratosthenes -

In this method we make an array prime[N] where prime[i]=1 means i is prime and prime[i]=0 means i is not prime. So we initially mark all elements in prime array as 1 denoting they all are prime, now mark prime[1]=0 and prime[1]=0 denoting 0 and 1 are not prime numbers.

Now iterate from 2 to whatever is limit ie.N now for each iteration check if prime[i]=1 and if it prime than it means all the number divisible by this number will not be prime. Like initially when we start from 2 we will encounter that 2 is prime, so now we will make another loop and mark all number divisible by 2 as not prime ie. we mark 4, 6, 8, 10..etc. as not prime by marking prime[j]=0 where j will be 2, 4 ,6, 8, 10....

Please youtube videos on Sieve of Eratosthenes it will be more easy to understand then.

Hope it helps.

Another Tutorial(Codeforces)

Format your code before posting it.

@aniruddha_98 it’s better if you write your code at www.ideone.com and paste link to that code here. :slight_smile:

1 Like