Sieve of Eratosthenes with Wheel Factorization
algorithm, c++, primes, sieve-of-eratosthenes, wheel-factorization
Solution
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.
Problem
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.