Revision as of 18:56, 12 November 2022 (view source) Nig (talk \| contribs) (→‎{{header\|AppleScript}}: Replaced my 2 previous scripts with a new one.) ← Older edit		Revision as of 19:49, 24 February 2023 (view source) Markjreed (talk \| contribs) m (Capitalization fix.) Newer edit →
Line 8: For example, the second-order wheel has circumference 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. Those that are multiples of 5 (only 2: 15 and 55) are obtained by multiplying the members of the second-order wheel. Removing them gives the next wheel, and so on. [https://www.youtube.com/watch?v=GxgGMwLfTjE ~~this~~This YouTube video] 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 wheel is represented by a sparse global array <tt>s</tt> such that for each member w of the wheel, <tt>s[w]</tt> contains the next member of the wheel; along with a similar "previous member" value, this allows numbers to be removed in a constant number of operations. But the simple abstract algorithm is based on an ordered set, and there is plenty of scope for different implementations. ;Task:

Sieve of Pritchard: Difference between revisions

Sieve of Pritchard (view source)

Revision as of 19:49, 24 February 2023