Sieve of Pritchard
In mathematics, the sieve of Pritchard is an algorithm for finding all prime numbers up to a specified bound.
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.
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.
Wheels are so-called because Wi can be usefully visualized as a circle of circumference Pi with its members marked at their corresponding distances from an origin.
The sieve of Pritchard is derived from the observation[1] that this holds generally: for all i > 0, the values in Wi → (p2i+1 − 1) are 1 and the primes between pi+1 and p2i+1.
The sieve of Pritchard as originally presented[2] 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.
[8] If the main loop terminates with a wheel whose length is less than N, it is extended up to N to generate the remaining primes.
In comparison, the natural version of Eratosthenes sieve (stopping at the same point) removes composite numbers 184 times.
The sieve of Pritchard can be expressed in pseudocode, as follows:[1] where next(W, w) is the next value in the ordered set W after w. where prev(W, w) is the previous value in the ordered set W before w. The algorithm can be initialized with W0 instead of W1 at the minor complication of making next(W, 1) a special case when k = 0.
Note that space needed for the primes is not counted, since they can printed or written to external storage as they are found.
Pritchard[2] presented a variant of his sieve that requires only O(N / log log N) 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.
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).
The sieve of Pritchard is unique in conflating the set of prime candidates with a dynamic wheel used to speed up the sifting process.
Examples are the use of the largest wheel of length not exceeding √N / log2 N to get a version of the sieve of Eratosthenes that takes O(N) additions and requires only O(√N / log log N) bits,[3] and the speedup of the naturally linear sieve of Atkin to get a sublinear optimized version.
