# SPOJ Problem 2 - Prime Generator

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?

• 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 Feb 18 '13 at 15:19
• 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. Nov 11 '14 at 16:55
• @DarthGizka: That wouldn't be recommended as it's someone else's code.
– Jamal
Nov 11 '14 at 16:58