# TLE help me optimise ..

Please help me optimise this solution to the Prime generator problem.

Any naive approach will not work. You need to use sieve of Eratosthenes.

Your code’s complexity is O(n^3). Learn this sieve of Eratosthenes algorithm then try.

If you face any problem here is my code-

``````
[1] (First try yourself)

[1]: http://www.spoj.com/submit/PRIME1/id=11771333``````

to test whether a given number n is prime or not you show know (all the prime nos that lie between 2 and sqrt(n)).after finding this you should check if n is not divisible by any of these numbers .if n satisfies this condition then n is a prime number.now in the given problem you should find all the prime numbers between m an n(both inclusive ).now here n can take a maximum value of 10^9. sqrt(10^9)<34000.hence find all the prime nos from 1 to 34000.use a good algorithm to do this.store them in an array . and use this array to generate all the prime numbers from m to n.this should work. here is my solution http://www.codechef.com/viewsolution/4109735

my code accepted on spoj but getting TLE at codechef…!
how is it possible ?

#include<stdio.h>
#include<math.h>
unsigned long long int m,n,t,i,j;
int main()
{

``````scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&m,&n);
if(m==1)
m++;
for(i=m;i<=n;i++)
{
int k=sqrt(i),l=0;
for(j=2;j<=k;j++)
{
if(i%j==0)
{
l++;
break;
}

}
if(l==0)
printf("%lld\n",i);

}
printf("\n");

}

return 0;
``````

}