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;
```

}