## Pritchard’s Wheel Sieve

### January 6, 2012

We have seen several different sieves that enumerate the prime numbers not greater than *n* due to Eratosthenes, Atkin, Euler and Sundaram. In the 1980s, Paul Pritchard, an Australian mathematician, developed a family of sieve algorithms based on wheels, eventually finding an algorithm with *O*(*n* / log log *n*) time complexity and *O*(√*n*) space complexity. We examine a simple version of Pritchard’s wheel sieve in today’s exercise.

We begin with some definitions. *M _{k}* is the product of the first

*k*primes; for instance,

*M*

_{7}= 2×3×5×7×11×13×17=510510. The totatives of

*M*are those numbers from 1 to

_{k}*M*that are coprime to

_{k}*M*(that is, they have no factors in common). It is easy to determine the totatives of

_{k}*M*by sieving: make a list of the integers from 1 to

_{k}*M*, then for each of the primes that form the product

_{k}*M*, strike out from the list the prime and all of its multiples; for instance, with

_{k}*M*

_{3}=2×3×5=30, sieving with 2 strikes out 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28 and 30, sieving with 3 strikes out 3, 6, 9, 12, 15, 18, 21, 24, 27, and 30, and sieving with 5 strikes out 5, 10, 15, 20, 25 and 30, leaving the totatives 1, 7, 11, 13, 17, 19, 23 and 29. A factoring wheel

*W*contains the gaps between successive totatives, wrapping around at the end; for instance,

_{k}*W*

_{3}consists of the gaps 6, 4, 2, 4, 2, 4, 6 and 2, corresponding to the gaps 7−1, 11−7, and so on, ending with 29−23 and 31−29 when the wheel wraps around at the end.

Pritchard’s wheel sieve uses wheels repeatedly to strike out composite numbers from the sieve. It operates in two phases: a setup phase and a processing loop.

The setup phase first computes a parameter *k* such that *M _{k}* < n / log

_{e}n <

*M*

_{k+1}, then computes the wheel

*W*and forms the set

_{k}*S*from 1 to

*n*by rolling the

*W*wheel. The setup phase also computes the list of

_{k}*m*primes not greater than the square root of

*n*.

We compute the primes not greater than 100 as an example. We compute k=2, since 100/log(100) is 21.714724 which is between *M*_{2}=6 and *M*_{3}=30. The *W*_{2} wheel is {4 2} and the set *S* is {1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97}; although there is only one set *S*, we will refer to this set as *S*_{2}, since it is the result of rolling the *W*_{2} wheel. Finally, the square root of 100 is 10, and the m=4 primes less than 10 are {2 3 5 7}.

The processing loop iterates from *k*+1 to *m*. At each loop we will strike some of the elements of *S*, reducing *S* from *S*_{k} to *S*_{k+1}. Each time through the loop we first identify *p*, the smallest member of *S* that is greater than 1, and strike it from the set *S*. We also strike from *S* the successive multiples *p*(*s*'−*s*) less than *n*, where *s*'−*s* are the successive gaps in *S*. Finally, we increment *k* by 1 and repeat the loop as long as *k*≤*m*.

In our example computing the primes not greater than 100, *i* will take the values 3 and 4. The first time through the loop, *p* = 5, the gaps are 5−1=4, 7−5=2, 11−7=4, 13−11=2, 17−13=4 and 19−17=2, and the numbers that are stricken are 5, 5+4×5=25, 25+2×5=35, 35+4×5=55, 55+2×5=65, 65+4×5=85, and 85+2×5=95, leaving *S*_{3} = {1 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97}. The second time through the loop, *p* = 7, the gaps are 7−1=6, 11−7=4, 13−11=6, 17−13=4, and 19−17=2, and the numbers that are stricken are 7, 7+6×7=49, 49+4×7=77, and 77+2×7=91, leaving *S*_{4} = {1 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97}.

Once *k*>*m* and the final *S* has been computed, the list of primes is returned, consisting of the primes less than the square root of *n* followed by the elements of *S* excluding 1. Thus the primes not greater than 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.

This version of Pritchard’s sieve has time complexity and space complexity both equal to *O*(*n*), where the standard sieve of Eratosthenes has time complexity *O*(*n* log log *n*). The improvement comes from the fact that Pritchard’s sieve strikes each composite only once, whereas Eratosthenes’ sieve strikes each composite once for each of its distinct prime factors; for instance, Eratosthenes’ sieve strike 15 twice, one for the factor of 3 and once for the factor of 5. But despite the improvement in the asymptotic complexity, Eratosthenes’ sieve is fast because its inner loop consists only of addition, while Pritchard’s sieve is slower because its inner loop consists of a subtraction to compute the gap in the wheel, a multiplication to extend that gap by the current sieving prime, and an addition to add the gap to the previously-stricken element. Thus, in practice, Eratosthenes’ sieve is faster than Pritchard’s.

Your task is to write a program to compute the primes not greater than *n* using Pritchard’s wheel sieve. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.