Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
GordonBGood (talk | contribs) →Fast infinite generator using a wheel: added a very large wheel with links to ideone.com |
m →Fast infinite generator using a wheel: corrected a typeo of 2/3/5/7/1/13/17 to 2/3/5/7/11/13/17. |
||
Line 3,730: | Line 3,730: | ||
for p, pi in wheel_prime_pairs(): yield p # strip out indexes</lang> |
for p, pi in wheel_prime_pairs(): yield p # strip out indexes</lang> |
||
Further gains of about 1.5 times in speed 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/ |
Further gains of about 1.5 times in speed 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/11/13/17 wheel (with the gaps list 92160 elements long) computed for a slight constant overhead time as per the [http://ideone.com/4Ld26g test link for Python 2.7] and [http://ideone.com/72Dmyt test link for Python 3.x]. Further wheel factorization will not really be worth it as the gains will be small (if any and not losses) and the gaps table huge - it is already too big for efficient use by 32-bit Python 3 and the wheel should likely be stopped at 13: |
||
<lang python>def primes(): |
<lang python>def primes(): |
||
whlPrms = [2,3,5,7,11,13,17] # base wheel primes |
whlPrms = [2,3,5,7,11,13,17] # base wheel primes |