3

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 ?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Green goblin
  • 9,898
  • 13
  • 71
  • 100
  • It's the best method *for certain a and b*. For numbers large enough for `b` bytes or bits to be too much space, there are other methods. But despite O(b) sounding scary, it can take you quite far -- one GB of memory should enable `b`s up to 8.5 billion (more than you can enumerate in 32 bit!) if you use a single bit per number. –  Sep 14 '12 at 19:11
  • Does there exist a way where i need a space equal to difference between a and b? Say, we know the range between a and b. – Green goblin Sep 14 '12 at 19:16
  • No, because you have to know all of the primes from 0 to a. Otherwise you can't run the sieve. – Jim Mischel Sep 14 '12 at 19:24
  • 5
    I think you only need the primes from 2 to sqrt(b), because if a number is composite, then at least one of the factors must be less than (or equal to) the sqrt. (Search for segmented sieve for more information) – Peter de Rivaz Sep 14 '12 at 19:33
  • 1
    @PeterdeRivaz, I think your approach is about testing one number for primality, which is different from applying the sieve algorithm to find all primes in a given range. The [Wikipedia page](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) distinguishes Trial Division as a separate technique. So it's not clear how this will help with the original question. – Hew Wolff Sep 14 '12 at 20:02
  • What are expected values of `a` and `b`? If `b-a` is relatively small, and `b` not too large, Peter de Rivaz' suggestion is the method of choice, `O(srt(b)/log b + (b-a))` space. If `b-a` is large, you should split that in chunks if you don't need to keep the primes (you just want to count or sum them or so), a chunk size of around `sqrt(b)` is sensible for `O(sqrt(b))` space. If `b` is too large to have the primes to `sqrt(b)` in memory, other methods are needed. You could sieve using smallish primes and some larger composites to cross off multiples, trading space for time. – Daniel Fischer Sep 15 '12 at 14:53
  • Can't you just start at a, use a primality test, and increment until you get to b? – Realz Slaw Sep 16 '12 at 02:32
  • @RealzSlaw using a primality test is not sieving. OTOH you can sieve by *odds* instead of *primes* and it too is O(1) additional space. For larger `b`'s and narrower ranges it will even be faster. :) I've added an answer about it. :) – Will Ness Sep 19 '12 at 15:30
  • @WillNess my point was that he can generate all the primes in [a,b] by primality testing, I think more efficiently that sieving. – Realz Slaw Sep 19 '12 at 15:50
  • 1
    @RealzSlaw [no it's not](http://www.wolframalpha.com/input/?i=Plot%5B+w*sqrt%28b%29%2F2+-+%28sqrt%28b%29%2F2++%2B+w*log%28b%29%2F8%29++%2C+%7Bb%2C+10%2C+2000000%7D%2C+%7Bw%2C20%2C10000%7D%5D). For very narrow ranges it's the same, but for any non-vanishing width sieving by odds is faster than testing by odds, because we test each, but when we sieve we skip over longer and longer spans (e.g.: `9,15,21...` or `121, 143, 165...`) and ***collect the primes in the gaps for free***. – Will Ness Sep 19 '12 at 16:02
  • @RealzSlaw ok, [it should've been (b-a)/log(b)*sqrt(b)/2](http://www.wolframalpha.com/input/?i=Plot%5B+w%2Flog%28b%29*sqrt%28b%29%2F2++-+%28sqrt%28b%29%2F2++%2B+w*log%28b%29%2F8%29++%2C+%7Bb%2C+10%2C+2000000%7D%2C+%7Bw%2C20%2C10000%7D%5D) (for *short-circuiting test* all odds will be used only in testing primes, and there are `(b-a)/log(b)` of those in the range `[a..b]`), but the conclusion is the same. – Will Ness Sep 19 '12 at 16:21

4 Answers4

5

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
2

Sorenson Sieve might be worth a peek if space complexity is really an issue. Got the reference from the wikipedia page you shared.

Karan Ashar
  • 1,392
  • 1
  • 10
  • 23
  • +1 though Sorensen is not a variant of Eratosthenes, but a totally different sieve, with worse time and better space complexity. BTW sieving by odds has probably even worse time cpxty, but it is O(1) additional space (besides the output). :) I've added an answer about it too. :) – Will Ness Sep 19 '12 at 15:27
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.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
1

Search for "segmented sieve of Eratosthenes" at your favorite search engine. If you don't want to go searching, I have an implementation at my blog.

user448810
  • 17,381
  • 4
  • 34
  • 59