|
[[Category:Simple]]
The [[wp:Sieve_of_Pritchard|Sieve of Pritchard]] is a modernan algorithm for finding the prime numbers up to a given limit N, published in 1981. It takesremoves many fewer operationscomposite numbers than the [[Sieve of Eratosthenes|Sieve of Eratosthenes]] (and has a better asymptotic time complexity). However, atunlike the costlatter, ofit greatercannot storagebe requirementsmodified (worseto greatly reduce its space complexity)requirement, making it unsuitable for very large limits.
Conceptually, it works by constructingbuilding a serieswheel ofrepresenting "wheels"the marked along their circumference with therepeating pattern of primesnumbers upnot todivisible theby valueone of successivethe primorialfirst numbersk (whereprimes, theincreasing Nthk primorial isuntil the productsquare of the firstk'th Nprime primes).is Thoseat wheelsleast areN. thenSince rolledwheels alonggrow the numbervery linequickly, andthe onlyalgorithm therestricts numbersattention touched byto the marksinitial areportions consideredof aswheels candidate primes, in contrastup to Eratosthenes'N. sieve(Small inexamples which allof the integerswheels inconstructed by the range start out as candidates. (The Sieve of Pritchard isare anused example ofin the "wheel-based optimizations" mentioned in the Eratosthenes task.)
For example, the second-order wheel has sizecircumference 6 (the product of the first two primes, 2 and 3) and is marked only at the numbers between 1 and 6 that are not multiples of 2 or 3, namely 1 and 5. As this wheel is rolled along the number line, it will pick up only numbers of the form 6k+1 or 6k+5 (that is, n where n mod 6 is in {1,5}). By the time it stops at 30 (2x3x5) it has added only 8 of the numbers between 6 and 30 as candidates for primality,. onlyThose onethat are multiples of which5 is(only actually2: composite1*5 and must5*5) beare removedobtained (25).by Inmultiplying the processmembers it has constructedof the nextsecond-order wheel,. whichRemoving willthem addgives onlythe ninenext outwheel, of every 30 numbers as it rolls upand toso 210on.
[https://www.youtube.com/watch?v=h9EHkZLekoYGxgGMwLfTjE Thisthis YouTube video] tells a story to help motivate the algorithm's design;[https://www.youtube.com/watch?v=GxgGMwLfTjE this one] presents the execution of the algorithm for N=150 in a format that permits single-stepping forward and backward through the run. In that implementation, the list of primeswheel is populatedrepresented intoby a sparse global array <tt>s</tt> such that for each member w of the wheel, <tt>s[pw]</tt> contains the next primemember afterof pthe iffwheel; palong is itselfwith a primesimilar in"previous themember" target range;value, this allows numbers to be removed fromin considerationa quicklyconstant withoutnumber anyof operations. But the copying/shiftingsimple thatabstract wouldalgorithm beis requiredbased fromon aan normally-packedordered arrayset, and there is plenty of scope for different implementations.
;Task:
|