Sieve of Eratosthenes: Difference between revisions
→Fast infinite generator using a wheel: added links to test implementations on ideone.com...
GordonBGood (talk | contribs) (→Infinite generator with a faster algorithm: added a link to ideone.com Python 3 implementation...) |
GordonBGood (talk | contribs) (→Fast infinite generator using a wheel: added links to test implementations on ideone.com...) |
||
Line 3,697:
===Fast infinite generator using a wheel===
Although theoretically over three times faster than odds-only, the following code using a 2/3/5/7 wheel is only about 1.5 times faster than the above odds-only code due to the extra overheads in code complexity, but further gains can be made using the same code by only changing the tables and a few constants for a further constant factor gain of about 1.5 times in speed by using a 2/3/5/7/1/13/17 wheel (with the gaps list 92160 elements long). These [http://ideone.com/LFaRnT test link for Python 2.7] and [http://ideone.com/ZAY0T2 test link for Python 3.x] show about the same empirical order of growth as the odds-only implementation above once the range grows enough so the dict operations become amortized to a constant factor.
{{works with|Python|2.6+, 3.x}}
<lang python>def primes():
| |||