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 CodeChef: Practical coding for everyone

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;

}