algorithm - 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

There are two basic choices here: sieve the range [a..b] by primes below sqrt(b) (the "offset" sieve of Eratosthenes), or by odd numbers. That's right; just eliminate the multiples of each odd as you would of each prime. Sieve the range in one chunk, or in several "segments" if the range is too wide (but efficiency can deteriorate if the chunks are too narrow).

In Haskell executable pseudocode,

-- foldl :: (r -> x -> r) -> r -> [x] -> r     -- type signature of foldl

primesRange_by_Odds a b = 
  foldl ( r x -> r `minus` [q x, q x+2*x .. b])
        [o, o+2 .. b]                          -- initial value of `r`, the list
        [3, 5 .. floor(sqrt(fromIntegral b))]  -- values of `x`, one after another
  where
    o   = 1 + 2*div a 2                        -- odd start of the range
    q x = x*x - 2*x*min 0 (div (x*x-o) (2*x))  -- 1st odd multiple of x >= x*x in range

Sieving by odds will have the additional space complexity of O(1) (on top of the output / range space of O(|b-a|)).

That is because we can enumerate the odds just by iteratively adding 2 – unlike the "core" primes for the sieve of Eratosthenes, below sqrt(b), for which we have to reserve additional space of O(pi(sqrt(b))) = ~ 2*sqrt(b)/log(b) (where pi() is the prime-counting function).

The remaining question is how do we find those "core" primes. Trial division will entail an additional space of O(1) but if we were to do it by the sieve of Eratosthenes, we'd need the O(sqrt(b)) space to perform the core sieve itself -- unless we perform it as a segmented sieve thus with the auxiliary space requirement of O(sqrt(sqrt(b))). Choose whatever method suits your needs better.