Sieve of Pritchard

Sieve of Pritchard: algorithm steps for primes up to 150

In mathematics, the sieve of Pritchard is an algorithm for finding all prime numbers up to a specified bound. Like the ancient sieve of Eratosthenes, it has a simple conceptual basis in number theory. It is especially suited to quick hand computation for small bounds.

Whereas the sieve of Eratosthenes marks off each non-prime for each of its prime factors, the sieve of Pritchard avoids considering almost all non-prime numbers by building progressively larger wheels, which represent the pattern of numbers not divisible by any of the primes processed thus far. It thereby achieves a better asymptotic complexity, and was the first sieve with a running time sublinear in the specified bound. Its asymptotic running-time has not been improved on, and it deletes fewer composites than any other known sieve. It was created in 1979 by Paul Pritchard.

Since Pritchard has created a number of other sieve algorithms for finding prime numbers, the sieve of Pritchard is sometimes singled out by being called the wheel sieve (by Pritchard himself) or the dynamic wheel sieve.

Overview

A prime number is a natural number that has no natural number divisors other than the number 1 and itself.

To find all the prime numbers less than or equal to a given integer Template:Mvar, a sieve algorithm examines a set of candidates in the range Template:Math, and eliminates those that are not prime, leaving the primes at the end. The sieve of Eratosthenes examines all of the range, first removing all multiples of the first prime 2, then of the next prime 3, and so on. The sieve of Pritchard instead examines a subset of the range consisting of numbers that occur on successive wheels, which represent the pattern of numbers left after each successive prime is processed by the sieve of Eratosthenes.

For Template:Math, the Template:Mvarth wheel Template:Math represents this pattern. It is the set of numbers between 1 and the product Template:Math of the first Template:Mvar prime numbers that are not divisible by any of these prime numbers (and is said to have an associated length Template:Math). This is because adding Template:Math to a number does not change whether it is divisible by one of the first Template:Mvar prime numbers, since the remainder on division by any one of these primes is unchanged.

So Template:Math with length Template:Math represents the pattern of odd numbers; Template:Math with length Template:Math represents the pattern of numbers not divisible by 2 or 3; etc. Wheels are so-called because Template:Math can be usefully visualized as a circle of circumference Template:Math with its members marked at their corresponding distances from an origin. Then rolling the wheel along the number line marks points corresponding to successive numbers not divisible by one of the first Template:Mvar prime numbers. The animation shows Template:Math being rolled up to 30.

Rolling the 2nd wheel up to 30.

It is useful to define Template:Math for Template:Math to be the result of rolling Template:Math up to Template:Mvar. Then the animation generates Template:Math. Note that up to Template:Math, this consists only of 1 and the primes between 5 and 25.

The sieve of Pritchard is derived from the observation that this holds generally: for all Template:Math, the values in Template:Math are 1 and the primes between Template:Math and Template:Math. It even holds for Template:Math, where the wheel has length 1 and contains just 1 (representing all the natural numbers). So the sieve of Pritchard starts with the trivial wheel Template:Math and builds successive wheels until the square of the wheel's first member after 1 is at least Template:Mvar. Wheels grow very quickly, but only their values up to Template:Mvar are needed and generated.

It remains to find a method for generating the next wheel. Note in the animation that Template:Math can be obtained by rolling Template:Math up to 30 and then removing 5 times each member of Template:Math.This also holds generally: for all Template:Math, Template:Math. Rolling Template:Math past Template:Math just adds values to Template:Math, so the current wheel is first extended by getting each successive member starting with Template:Math, adding Template:Math to it, and inserting the result in the set. Then the multiples of Template:Math are deleted. Care must be taken to avoid a number being deleted that itself needs to be multiplied by Template:Math. The sieve of Pritchard as originally presented does so by first skipping past successive members until finding the maximum one needed, and then doing the deletions in reverse order by working back through the set. This is the method used in the first animation above. A simpler approach is just to gather the multiples of Template:Math in a list, and then delete them. Another approach is given by Gries and Misra.

If the main loop terminates with a wheel whose length is less than Template:Mvar, it is extended up to Template:Mvar to generate the remaining primes.

The algorithm, for finding all primes up to Template:Mvar, is therefore as follows:

1. Start with a set Template:Math and Template:Math representing wheel 0, and prime Template:Math.
2. As long as Template:Math, do the following:
   1. if Template:Math, then
      1. extend Template:Mvar by repeatedly getting successive members Template:Mvar of Template:Mvar starting with 1 and inserting Template:Math into Template:Mvar as long as it does not exceed Template:Math or Template:Mvar;
      2. increase Template:Mvar to the minimum of Template:Math and Template:Mvar.
   2. repeatedly delete Template:Mvar times each member of Template:Mvar by first finding the largest Template:Math and then working backwards.
   3. note the prime Template:Mvar, then set Template:Mvar to the next member of Template:Mvar after 1 (or 3 if Template:Mvar was 2).
3. if Template:Math, then extend Template:Mvar to Template:Mvar by repeatedly getting successive members Template:Mvar of Template:Mvar starting with 1 and inserting Template:Math into Template:Mvar as long as it does not exceed Template:Mvar;
4. On termination, the rest of the primes up to Template:Mvar are the members of Template:Mvar after 1.

Example

To find all the prime numbers less than or equal to 150, proceed as follows.

Start with wheel 0 with length 1, representing all natural numbers 1, 2, 3...:

  1

The first number after 1 for wheel 0 (when rolled) is 2; note it as a prime. Now form wheel 1 with length 2Template:Times1 = 2 by first extending wheel 0 up to 2 and then deleting 2 times each number in wheel 0, to get:

  1 Template:Gray

The first number after 1 for wheel 1 (when rolled) is 3; note it as a prime. Now form wheel 2 with length 3Template:Times2 = 6 by first extending wheel 1 up to 6 and then deleting 3 times each number in wheel 1, to get

  1 Template:Gray Template:Gray 5

The first number after 1 for wheel 2 is 5; note it as a prime. Now form wheel 3 with length 5Template:Times6 = 30 by first extending wheel 2 up to 30 and then deleting 5 times each number in wheel 2 (in reverse order!), to get

  1 Template:Gray Template:Gray Template:Gray 7 11 13 17 19 23 Template:Gray 29

The first number after 1 for wheel 3 is 7; note it as a prime. Now wheel 4 has length 7Template:Times30 = 210, so we only extend wheel 3 up to our limit 150. (No further extending will be done now that the limit has been reached.) We then delete 7 times each number in wheel 3 until we exceed our limit 150, to get the elements in wheel 4 up to 150:

  1 Template:Gray Template:Gray Template:Gray Template:Gray 11 13 17 19 23 Template:Gray 29 31 37 41 43 47 Template:Gray 53 59 61 67 71 73 Template:Gray 79 83 89 Template:Gray 97 101 103 107 109 113 Template:Gray 121 127 131 Template:Gray 137 139 143 149

The first number after 1 for this partial wheel 4 is 11; note it as a prime. Since we have finished with rolling, we delete 11 times each number in the partial wheel 4 until we exceed our limit 150, to get the elements in wheel 5 up to 150:

  1 Template:Gray Template:Gray Template:Gray Template:Gray Template:Gray 13 17 19 23 Template:Gray 29 31 37 41 43 47 Template:Gray 53 59 61 67 71 73 Template:Gray 79 83 89 Template:Gray 97 101 103 107 109 113 Template:Gray Template:Gray 127 131 Template:Gray 137 139 Template:Gray 149

The first number after 1 for this partial wheel 5 is 13. Since 13 squared is at least our limit 150, we stop. The remaining numbers (other than 1) are the rest of the primes up to our limit 150.

Just 8 composite numbers are removed, once each. The rest of the numbers considered (other than 1) are prime. In comparison, the natural version of Eratosthenes sieve (stopping at the same point) removes composite numbers 184 times.

Pseudocode

The sieve of Pritchard can be expressed in pseudocode, as follows:

algorithm Sieve of Pritchard is
    input: an integer N >= 2.
    output: the set of prime numbers in {1,2,...,N}.

    let W and Pr be sets of integer values, and all other variables integer values.
    k, W, length, p, Pr := 1, {1}, 2, 3, {2};
    {invariant: p = pk+1 and W = Wk $\cap$ {1,2,...,N} and length = minimum of Pk,N and Pr = the primes up to pk}
    while p2 <= N do
        if (length < N) then
            Extend W,length to minimum of p*length,N; 
        Delete multiples of p from W; 
        Insert p into Pr; 
        k, p := k+1, next(W, 1) 
    if (length < N) then
        Extend W,length to N;

    return Pr $\cup$ W - {1};

where Template:Tt is the next value in the ordered set Template:Mvar after Template:Mvar.

procedure Extend W,length to n is
    {in: W = Wk and length = Pk and n > length}
    {out: W = Wk$\to$n and length = n}

    integer w, x;
    w, x := 1, length+1;
    while x <= n do
        Insert x into W;
        w := next(W,w);
        x := length + w;
    length := n;

procedure Delete multiples of p from W,length is
    integer w;
    w := p;
    while p*w <= length do
        w := next(W,w);
    while w > 1 do
        w := prev(W,w);
        Remove p*w from W;

where Template:Tt is the previous value in the ordered set Template:Mvar before Template:Mvar. The algorithm can be initialized with Template:Math instead of Template:Math at the minor complication of making Template:Tt a special case when Template:Tt.

This abstract algorithm uses ordered sets supporting the operations of insertion of a value greater than the maximum, deletion of a member, getting the next value after a member, and getting the previous value before a member. Using one of Mertens' theorems (the third) it can be shown to use Template:Math of these operations and additions and multiplications.

Implementation

An array-based doubly-linked list Template:Tt can be used to implement the ordered set Template:Tt, with Template:Tt storing Template:Tt and Template:Tt storing Template:Tt. This permits each abstract operation to be implemented in a small number of operations. (The array can also be used to store the set Template:Tt "for free".) Therefore the time complexity of the sieve of Pritchard to calculate the primes up to Template:Mvar in the random access machine model is Template:Math operations on words of size Template:Math. Pritchard also shows how multiplications can be eliminated by using very small multiplication tables, so the bit complexity is Template:Math bit operations.

In the same model, the space complexity is Template:Math words, i.e., Template:Math bits. The sieve of Eratosthenes requires only 1 bit for each candidate in the range 2 through Template:Mvar, so its space complexity is lower at Template:Math bits. Note that space needed for the primes is not counted, since they can printed or written to external storage as they are found. Pritchard presented a variant of his sieve that requires only Template:Math bits without compromising the sublinear time complexity, making it asymptotically superior to the natural version of the sieve of Eratostheses in both time and space.

However, the sieve of Eratostheses can be optimized to require much less memory by operating on successive segments of the natural numbers. Its space complexity can be reduced to Template:Math bits without increasing its time complexity. This means that in practice it can be used for much larger limits Template:Mvar than would otherwise fit in memory, and also take advantage of fast cache memory. For maximum speed, it is also optimized using a small wheel to avoid sieving with the first few primes (although this does not change its asymptotic time complexity). Therefore the sieve of Pritchard is not competitive as a practical sieve over sufficiently large ranges.

Geometric model

Generating successive wheels up to $W_3$

At the heart of the sieve of Pritchard is an algorithm for building successive wheels. It has a simple geometric model as follows:

1. Start with a circle of circumference 1 with a mark at 1.
2. To generate the next wheel:
   1. Go around the wheel and find (the distance to) the first mark after 1; call it Template:Mvar.
   2. Create a new circle with Template:Mvar times the circumference of the current wheel.
   3. Roll the current wheel around the new circle, marking it where a mark touches it.
   4. Magnify the current wheel by Template:Mvar and remove the marks that coincide.

For the first 2 iterations it is necessary to continue round the circle until 1 is reached again.

The first circle represents Template:Math, and successive circles represent wheels Template:Math. The animation on the right shows this model in action up to Template:Math.

It is apparent from the model that wheels are symmetric. This is because Template:Math is not divisible by one of the first Template:Mvar primes if and only if Template:Mvar is not so divisible. It is possible to exploit this to avoid processing some composites, but at the cost of a more complex algorithm.

Related sieves

Once the wheel in the sieve of Pritchard reaches its maximum size, the remaining operations are equivalent to those performed by Euler's sieve.

The sieve of Pritchard is unique in conflating the set of prime candidates with a dynamic wheel used to speed up the sifting process. But a separate static wheel (as frequently used to speed up the sieve of Eratosthenes) can give an Template:Math speedup to the latter, or to linear sieves, provided it is large enough (as a function of Template:Mvar). Examples are the use of the largest wheel of length not exceeding Template:Math to get a version of the sieve of Eratosthenes that takes Template:Math additions and requires only Template:Math bits, and the speedup of the naturally linear sieve of Atkin to get a sublinear optimized version.

Bengalloun found a linear smoothly incremental sieve, i.e., one that (in theory) can run indefinitely and takes a bounded number of operations to increment the current bound Template:Mvar. He also showed how to make it sublinear by adapting the sieve of Pritchard to incrementally build the next dynamic wheel while the current one is being used. Pritchard showed how to avoid multiplications, thereby obtaining the same asymptotic bit-complexity as the sieve of Pritchard.

Runciman provides a functional algorithm inspired by the sieve of Pritchard.

See also

• Sieve of Eratosthenes
• Sieve of Atkin
• Sieve theory
• Wheel factorization