Rosetta Code

Sieve of Eratosthenes: Difference between revisions

Page Discussion

Sieve of Eratosthenes (view source)

Revision as of 05:57, 10 May 2014

1 byte added ,  10 years ago
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.
(→‎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:
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/111/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():
whlPrms = [2,3,5,7,11,13,17] # base wheel primes
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/38963"