Revision as of 19:49, 24 February 2023 (view source) Markjreed (talk \| contribs) m (Capitalization fix.) ← Older edit		Revision as of 19:50, 24 February 2023 (view source) Markjreed (talk \| contribs) m (Clarify wording.) Newer edit →
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 ~~removes~~considers many fewer composite numbers than the [[Sieve of Eratosthenes\|Sieve of Eratosthenes]] (and has a better asymptotic time complexity). However, unlike the latter, it cannot be modified to greatly reduce its space requirement, making it unsuitable for very large limits. 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.)

Sieve of Pritchard: Difference between revisions

Sieve of Pritchard (view source)