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.

Sieve of 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.

Sieve of Pritchard

Overview

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

Sieve of Pritchard

To find all the prime numbers less than or equal to a given integer , a sieve algorithm examines a set of candidates in the range , 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 , then of the next prime , 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 the 'th wheel represents this pattern. It is the set of numbers between and the product of the first prime numbers that are not divisible by any of these prime numbers (and is said to have an associated length ). This is because adding to a number doesn't change whether or not it is divisible by one of the first prime numbers, since the remainder on division by any one of these primes is unchanged.

So with length represents the pattern of odd numbers; with length represents the pattern of numbers not divisible by or ; etc. Wheels are so-called because can be usefully visualized as a circle of circumference 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 prime numbers. The animation shows being rolled up to 30.

It's useful to define for to be the result of rolling up to . Then the animation generates . Note that up to , this consists only of and the primes between and .

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

It remains to find a method for generating the next wheel. Note in the animation that can be obtained by rolling up to and then removing times each member of . This also holds generally: for all , . Rolling past just adds values to , so the current wheel is first extended by getting each successive member starting with , adding to it, and inserting the result in the set. Then the multiples of are deleted. Care must be taken to avoid a number being deleted that itself needs to be multiplied by . 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 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 , it is extended up to to generate the remaining primes.

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