SPOJ Problem 2 - Prime Generator

Question

I'm trying to solve this problem. After a couple of tries, this is what I pulled 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 a long int on a 32-bit machine (2,147,483,647). For the same purpose, I used while (k<46340 && (k-Start2 <100000)).

This code exceeds the time limit (6 seconds) of the SPOJ problem rule.

How can this be faster?

• cat_baxter: You should use the 'Segmented Sieve' algorithm. If you need the complete explanation of the problem look here: zobayer.blogspot.de/2009/09/segmented-sieve.html
• DarthGizka: cat_baxter, why should anyone look at that horrible code? Post it for review to find out all the things that are wrong with it.
• Jamal: @DarthGizka: That wouldn't be recommended as it's someone else's code.

Answer 1

The short answer: restrict your sieving to what is necessary (sieve potential factors up to the square root of the upper end of the range, sieve the range itself). The runtime for that is a few milliseconds, compared to several seconds (or even minutes) for sieving all numbers up to the upper end of the range.

An extensive answer with all the bells and whistles is at StackOverflow, where the SPOJ PRIME1 question has already been asked and answered:

How do I efficiently sieve through a selected range for prime numbers?

In addition to what is said there: trial division is the slowest form of primality test ever. The Sieve of Eratosthenes is equally simple but it is the fastest of them all, for small numbers up to 2^64 or thereabouts. Special requirements like that of SPOJ PRIME1 require small complications - e.g. windowed/segmented operation - and there are many complications that can be added to make it even faster if that is desired. See the linked article. However, for SPOJ I would keep things sweet and simple.