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.^[1] 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.^[2]

Since Pritchard has created a number of other sieve algorithms for finding prime numbers,^[3][4][5] the sieve of Pritchard is sometimes singled out by being called the wheel sieve (by Pritchard himself^[1]) or the dynamic wheel sieve.^[6]

Overview

A prime number is a natural number that has no natural number divisors other than the number ${\displaystyle 1}$ and itself.

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

So ${\displaystyle W_{1}=\{1\}}$ with length ${\displaystyle P_{1}=2}$ represents the pattern of odd numbers; ${\displaystyle W_{2}=\{1,5\}}$ with length ${\displaystyle P_{2}=6}$ represents the pattern of numbers not divisible by ${\displaystyle 2}$ or ${\displaystyle 3}$; etc. Wheels are so-called because ${\displaystyle W_{i}}$ can be usefully visualized as a circle of circumference ${\displaystyle P_{i}}$ 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 ${\displaystyle i}$ prime numbers. The animation shows ${\displaystyle W_{2}}$ being rolled up to 30.

It's useful to define ${\displaystyle W_{i}\rightarrow n}$ for ${\displaystyle n>0}$ to be the result of rolling ${\displaystyle W_{i}}$ up to ${\displaystyle n}$. Then the animation generates ${\displaystyle W_{2}\rightarrow 30=\{1,5,7,11,13,17,19,23,25,29\}}$. Note that up to ${\displaystyle 5^{2}-1=24}$, this consists only of ${\displaystyle 1}$ and the primes between ${\displaystyle 5}$ and ${\displaystyle 25}$.

The sieve of Pritchard is derived from the observation^[1] that this holds generally: for all ${\displaystyle i>0}$, the values in ${\displaystyle W_{i}\rightarrow {(p_{i+1}^{2}-1)}}$ are ${\displaystyle 1}$ and the primes between ${\displaystyle p_{i+1}}$ and ${\displaystyle p_{i+1}^{2}}$. It even holds for ${\displaystyle i=0}$, where the wheel has length ${\displaystyle 1}$ and contains just ${\displaystyle 1}$ (representing all the natural numbers). So the sieve of Pritchard starts with the trivial wheel ${\displaystyle W_{0}}$ and builds successive wheels until the square of the wheel's first member after ${\displaystyle 1}$ is at least ${\displaystyle N}$. Wheels grow very quickly, but only their values up to ${\displaystyle N}$ are needed and generated.

It remains to find a method for generating the next wheel. Note in the animation that ${\displaystyle W_{3}=\{1,5,7,11,13,17,19,23,25,29\}-\{5*1,5*5\}}$ can be obtained by rolling ${\displaystyle W_{2}}$ up to ${\displaystyle 30}$ and then removing ${\displaystyle 5}$ times each member of ${\displaystyle W_{2}}$. This also holds generally: for all ${\displaystyle i\geq 0}$, ${\displaystyle W_{i+1}=}$Zdroj:https://en.wikipedia.org?pojem=Sieve_of_Pritchard
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.