Sieve of Eratosthenes with Wheel Factorization

Question

I'm implementing a reasonably fast prime number generator and I obtained some nice results with a few optimizations on the sieve of Eratosthenes. In particular, during the preliminary part of the algorithm, I skip all multiples of 2 and 3 in this way:

template<class Sieve, class SizeT>
void PrimeGenerator<Sieve, SizeT>::factorize()
{
    SizeT c = 2;
    m_sieve[2] = 1;
    m_sieve[3] = 1;

    for (SizeT i=5; i<m_size; i += c, c = 6 - c)
        m_sieve[i] = 1;
}

Here m_sieve is a boolean array according to the sieve of Eratosthenes. I think this is a sort of Wheel factorization only considering primes 2 and 3, incrementing following the pattern 2, 4, 2, 4,..

What I would like to do is to implement a greater wheel, maybe considering primes 2,3 and 5.

I already read a lot of documentation about it, but I didn't see any implementation with the sieve of Eratosthenes... a sample code could help a lot, but also some hints would be nice :) Thanks.

Answer 1

You can go even further. Here is some OCaml code I wrote a few years ago:

let eratosthene borne =
  let remove_multiples a lst =
    let rec remmult multa li accu = function
        []         -> rev accu
      | head::tail ->
          if multa = head
          then remmult (a*(hd li)) (tl li)  accu      tail
          else remmult   multa        li (head::accu) tail
    in
    remmult (a * a) lst [] lst
  in
  let rec first_primes accu ll =
    let a = hd ll in 
    if a * a > borne then (rev accu) @ ll 
    else first_primes (a::accu) (remove_multiples a (tl ll))
  in
  let start_list =
(* Hard code of the differences of consecutive numbers that are prime*)
(* with 2 3 5 7 starting with 11... *) 
    let rec lrec = 2 :: 4 :: 2 :: 4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 6
      :: 6 :: 2 :: 6 :: 4 :: 2 :: 6 :: 4 :: 6 :: 8 :: 4 :: 2 :: 4 :: 2
      :: 4 :: 8 :: 6 :: 4 :: 6 :: 2 :: 4 :: 6 :: 2 :: 6 :: 6 :: 4 :: 2
      :: 4 :: 6 :: 2 :: 6 :: 4 :: 2 :: 4 :: 2 :: 10 :: 2 :: 10 :: lrec 
    and listPrime2357 a llrec accu =
      if a > borne then rev accu
      else listPrime2357 (a + (num (hd llrec))) (tl llrec) (a::accu)
    in
    listPrime2357 (num 11) lrec []
  in
  first_primes [(num 7);(num 5);(num 3);(num 2)] start_list;;

Note the nice trick that OCaml allows for cyclic linked list.

Answer 2

Paul Pritchard, an Australian mathematician working for IBM, developed a series of wheel sieves in the 1980s. I discuss one of them at my blog, including examples worked by hand and an implementation in Scheme. It's too big to discuss here. You should be aware that though the asymptotic complexity is less than the Sieve of Eratosthenes, implementation details typically make it slower in practice.