Sieve of Pritchard

The sieve of Pritchard is an algorithm for finding all prime numbers up to a specified limit, created by Paul Pritchard in 1979. Unlike the ancient sieve of Eratosthenes, which marks each composite number once for every prime factor it has, Pritchard's method avoids most composite numbers entirely by building progressively larger wheels representing the pattern of numbers not divisible by any prime processed so far, which is why it is sometimes called the wheel sieve or dynamic wheel sieve. This approach gives it better asymptotic time complexity than the sieve of Eratosthenes, and it was the first sieve algorithm shown to run in time sublinear in the bound being sieved to; it also examines fewer composite numbers than any competing sieve algorithm. The sieve of Pritchard is well suited to hand calculation for small bounds, though for very large ranges the sieve of Eratosthenes, optimized with a segmented approach, remains more practical because of its lower memory requirements. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/