Sieve of Pritchard: Difference between revisions
Content added Content deleted
m (Capitalization fix.) |
m (Clarify wording.) |
||
| Line 2: | Line 2: | ||
[[Category:Simple]] |
[[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 |
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 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.) |
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.) |
||