How can wheel factorization be used to speed up sieving?

Question

I've seen optimizations to the Sieve of Eratosthenes that (claim to) use "wheel factorization". If the goal is to generate a list of prime numbers up to a certain value, I'm wondering how exactly is wheel factorization used? The Wikipedia article contains some information but it doesn't make sense to me.

For example sieve up to $15$: $\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}$
Starting with 2 strike off multiples $\{1,2,3,\_,5,\_,7,\_,9,\_,11,\_,13,\_,15\}$
Then strike off multiples of 3: $\{1,2,3,\_,5,\_,7,\_,\_,\_,11,\_,13,\_,\_\}$

For wheel factorization with base primes $2$ and $3$ the idea is composites occur periodically with 3 in a row, then one.

So how are these two ideas "merged" when creating a list of prime numbers? Is it just wheel factorization is used to create an initial list of candidates before sieving? But that doesn't seem to save any time because SoE has the pitfall where it strikes off all ready stricken off composites (for example 15 is stricken off on 3 and 15 so what good would wheel factorization of circumference 6 do)?

Is anyone able to provide an example of wheel factorization used with a sieve?

TL;DR how is wheel factorization used with sieving?

Answer 1

Let's say you have the wheel made from the first $3$ prime numbers: $2, 3, 5$. The wheel would consist of all integer $n \in [2, 2\cdot 3\cdot 5 + 1]$ coprime to $2, 3, 5$. Specifically it would be $\{7, 11, 13, 17, 19, 23, 29, 31 \}$.

Let's say you are trying to find all primes under $600$. Then the candidate list of primes would be given by almost $20$ "spins" of the wheel. It would be $\{ 7, 11, 13, 17, 19, 23, 29, 31, 7+30, 11+30, 13+30, 17+30, 19+30, 23+30, 29+30, 31+30..., 599\}$

The cutoff is $599$ here because the next element of $601$ would be above the limit of $600$.

Then the algorithm would be:

p = first element = 7
while p <= sqrt(N) = sqrt(600)
  if p is a prime (i.e. not marked as false)
    mark multiples of p in candidate prime list as false (except for p itself)
  set p to next element

The advantage to the plain Sieve of Eratosthenes is in the set p to next element step. Because of the wheel, $p$ would increment faster on average. While for the original sieve, you would have had to increment through every single integer $\ge 2$, now you can increment through only $8/30$ (on average).

You may have even used a simple form of wheel factoring in a sieve. Incrementing over the odd numbers is wheel factoring, just with only the first prime number, $2$.

Answer 2

An example of how to use wheel factorization with sieve to find primes greater than $3$ is the following:

code in python

n=10000000
primes5mod6 = [True] * (n//6+1)
primes1mod6 = [True] * (n//6+1)
for i in range(1,int((n**0.5+1)/6)+1):
    if primes5mod6[i]:
        primes5mod6[6*i*i::6*i-1]=[False]*((n//6-6*i*i)//(6*i-1)+1)
        primes1mod6[6*i*i-2*i::6*i-1]=[False]*((n//6-6*i*i+2*i)//(6*i-1)+1)
    if primes1mod6[i]:
        primes5mod6[6*i*i::6*i+1]=[False]*((n//6-6*i*i)//(6*i+1)+1)
        primes1mod6[6*i*i+2*i::6*i+1]=[False]*((n//6-6*i*i-2*i)//(6*i+1)+1)

then for $i>0$

$ p = 6i-1 \quad $ is prime if $ \quad primes5mod6 [i] = True $

and

$ p = 6i + 1 \quad$ is prime if $\quad primes1mod6 [i] = True $

In this way multiples of $2$ and $3$ are skipped as in the wheel but the sieve is also used.

I update the answer with some images that allow to visualize the difference between the traditional sieve and three optimizations with wheel

wheel with base prime $2$

and wheel with base primes $2$ and $3$

In this case it can be seen that in row $\quad 1\pmod 6 \quad$ the starting value to eliminate multiples is $\quad p\cdot p \quad$ instead in row $\quad 5\pmod 6 \quad$ the starting value is $\quad p\cdot (p+2) \quad$ if $\quad p\equiv 5\pmod 6 \quad$ or $\quad p\cdot (p-2)\quad$ if $\quad p\equiv 1\pmod 6$

Finally, this is the case wheel with base primes $2$ , $3$ and $5$

As it is possible to visualize the multiples of the prime numbers of the base are not considered in this way it uses less memory and an increase in speed.