Sieve of Pritchard: Difference between revisions
m
Clarify wording.
m (Capitalization fix.) |
m (Clarify wording.) |
||
Line 2:
[[Category:Simple]]
The [[wp:Sieve_of_Pritchard|Sieve of Pritchard]] is an algorithm for finding the prime numbers up to a given limit N, published in 1981. It
Conceptually, it works by building a wheel representing the repeating pattern of numbers not divisible by one of the first k primes, increasing k until the square of the k'th prime is at least N. Since wheels grow very quickly, the algorithm restricts attention to the initial portions of wheels up to N. (Small examples of the wheels constructed by the Sieve of Pritchard are used in the "wheel-based optimizations" mentioned in the Eratosthenes task.)
|