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?