TLE help me optimise ..

general
, , ,
1

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

2

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
3

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

4

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;

}