Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Trying to solve this problem. After couple of tries this is what i could pull off

        #include<stdio.h>
    #define primeLimit 100000


    int prime (long int Start2,  long int Stop2 )
    {
       long int a[primeLimit+1];
       long int i,j,k,l;
       for (i=Start2;i<=Stop2;i++)
       {
           a[i-Start2] = 1;
       }


       for (i=Start2;i<=Stop2;i++)
       {
            if (a[i-Start2]!= 0 && i!=1)
            {
                for (j=3; j*j< i;j=j+2)
                {
                    if(i%j==0)
                        break;

                }
                if(j*j > i)
                {
                    printf(" \n %ld",i);
                    l = i;
                    if (i<=46340)
                    {
                    for (k = i*i; k< Stop2;)
                         {
                                while (k<46340 && (k-Start2 <100000))
                                a[k-Start2] = 0;
                                k = k+l;

                         }
                    }
                }
                else
                {
                    a[i-Start2] = 0;
                }
            }
       }

        return 0;
    }



    int main (void)
    {

       long int start,stop,a,look;

       scanf("%ld", &look);

       for (a=1;a<=look;a++)
       {
           scanf("%ld %ld", &start,&stop);
            prime (start,stop);
       }

       return 0;
    }

Here i used if (i<=46340) because the 46340*46340 exceeds the limit of an long int in 32 bit machine(2,147,483,647). For the same purpose i used while (k<46340 && (k-Start2 <100000)) condition.

Any idea on making this code better and faster will be hugely appreciated.

Thank You

P.S. this code exceeds the time limit(6 seconds) of the SPOJ problem rule.

share|improve this question
add comment

2 Answers

Have a think about how long your program takes. For each prime number i in the range, you look at all numbers j from 3 upwards until you find a factor of i (which, since i is prime, must be i itself). The prime number theorem says that about 1 in every log n numbers near n is prime, so in order to find the primes from 105 numbers near 109 (the worst case that SPOJ might throw at you) you have to compute about

105 · 109 / log 109 = ~ 5 · 1012

divisions. So no wonder this takes a long time.

In order to improve things, you need a better algorithm, and a good place to look for one is the Wikipedia article on primality tests, where you'll see that there are fast randomized algorithms for primality testing, for example Miller–Rabin.

For this challenge, you could get away with using a pure Miller–Rabin test, but for even faster results, a hybrid approach is probably best: that is, to do trial division by a table of small prime numbers to reject most numbers, and then to apply Miller–Rabin for all the numbers that pass.

share|improve this answer
add comment

You should use the 'Segmented Sieve' algorithm. If you need the complete explanation of the problem look here: http://zobayer.blogspot.de/2009/09/segmented-sieve.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.