# SPOJ problem2 Prime Generator : How to make my code better and faster? (in C)

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.

-

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.

-