Segmented Sieve of Eratosthenes

If you have enough space to store all primes upto sqrt(b) then you can sieve for primes in the range a to b using additional space O(b - a) :

To do this let us take an example of the #SPOJ problem 2 : PRIME1 where we are given the upper limit as 1000000000 which is quite big if we want to store all the numbers in an array although we can store them by reducing them to array where each bit of a number stores whether the corresponding number is a prime or not i.e. if there are 64 numbers in the sieve we need two integers of 32 bits to store information of whether the number is prime or not.

Another method is if you have space to store upto square root of upper limit using sieve of eratosthenes then we can calculate the sieve of b-a from the sieve already present. The way to do it is mentioned below :

1. First get the sieve upto the square root of upper limit which in this case is  1000000000.  For 1000000000 the square root comes near 31625. Hence we create an array pre_sieve[31625] and fill it with the values:

pre_sieve[31265] = {1};
for(int i=2;i<=177;i++)
{
    if(pre_sieve[i] == 1)
    {
         for(int j = i*i;j< = 31264; j+=i)
             pre_sieve[j] = 0;
    }
} 
vector<int> primes;
for(int i=2;i<=31264;i++)
if(pre_sieve[i] == 1)
    primes.push_back(i);
 

Now for a range [a,b] we need to find the closest number that is in the range and is a composite number of the prime p. To do this we can divide the start of the range by p and take the floor and then multiply the resulting by p.We can then iterate in the sieve to get the primes.

for(int i=0;i<primes.size();i++)
{
     int *arr = (int *)malloc(sizeof(int)*(b-a+1));
     memset(arr,1,b-a+1);
     int prime = primes[i];
     int low = a/prime;
     low = low * prime;
     for(int j = low * 2;j<=b;j+= prime)
             arr[j] = 0 
}

Again you can reduce the space further by only sieving the odd number.