Reducing space complexity of Sieve of Eratosthenes to generate primes in a range

Question

After getting through some of the SO posts, I found Sieve of Eratosthenes is the best & fastest way of generating prime numbers.

I want to generate the prime numbers between two numbers, say a and b.

AFAIK, in Sieve's method, the space complexity is O(b).

PS: I wrote Big-O and not Theta, because I don't know whether the space requirement can be reduced.

Can we reduce the space complexity in Sieve of Eratosthenes ?

Answer 1

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

In Python this might look like:

def primesieve(ps,start,n):
  """Sieve the interval [start,start+n) for primes.

     Returns a list P of length n.  
     P[x]==1 if the number start+x is prime.  
     Relies on being given a list of primes in ps from 2 up to sqrt(start+n)."""
  P=[1]*n
  for p in ps:
    for k in range((-start)%p,n,p):
      if k+start<=p: continue
      P[k]=0
  return P

You could easily make this take half the space by only sieving the odd numbers.