fork(2) download
copy 
  1. # from:  http://r...content-available-to-author-only...e.org/wiki/Sieve_of_Eratosthenes#Fast_infinite_generator_using_a_wheel
  2.  
  3. def primes():
  4.     whlPrms = [2,3,5,7,11,13,17]                # base wheel primes
  5.     for p in whlPrms: yield p
  6.     def makeGaps():
  7.         buf = [True] * (3 * 5 * 7 * 11 * 13 * 17 + 1) # all odds plus extra for o/f
  8.         for p in whlPrms:
  9.             if p < 3:
  10.                 continue              # no need to handle evens
  11.             strt = (p * p - 19) >> 1            # start position (divided by 2 using shift)
  12.             while strt < 0: strt += p
  13.             buf[strt::p] = [False] * ((len(buf) - strt - 1) // p + 1) # cull for p
  14.         whlPsns = [i + i for i,v in enumerate(buf) if v]
  15.         return [whlPsns[i + 1] - whlPsns[i] for i in xrange(len(whlPsns) - 1)]
  16.     gaps = makeGaps()                           # big wheel gaps
  17.     def wheel_prime_pairs():
  18.         yield (19,0); bps = wheel_prime_pairs() # additional primes supply
  19.         p, pi = next(bps); q = p * p            # adv to get 11 sqr'd is 121 as next square to put
  20.         sieve = {}; n = 23; ni = 1              #   into sieve dict; init cndidate, wheel ndx
  21.         while True:
  22.             if n not in sieve:                  # is not a multiple of previously recorded primes
  23.                 if n < q: yield (n, ni)         # n is prime with wheel modulo index
  24.                 else:
  25.                     npi = pi + 1                # advance wheel index
  26.                     if npi > 92159: npi = 0
  27.                     sieve[q + p * gaps[pi]] = (p, npi) # n == p * p: put next cull position on wheel
  28.                     p, pi = next(bps); q = p * p  # advance next prime and prime square to put
  29.             else:
  30.                 s, si = sieve.pop(n)
  31.                 nxt = n + s * gaps[si]          # move current cull position up the wheel
  32.                 si = si + 1                     # advance wheel index
  33.                 if si > 92159: si = 0
  34.                 while nxt in sieve:             # ensure each entry is unique by wheel
  35.                     nxt += s * gaps[si]
  36.                     si = si + 1                 # advance wheel index
  37.                     if si > 92159: si = 0
  38.                 sieve[nxt] = (s, si)            # next non-marked multiple of a prime
  39.             nni = ni + 1                        # advance wheel index
  40.             if nni > 92159: nni = 0
  41.             n += gaps[ni]; ni = nni             # advance on the wheel
  42.     for p, pi in wheel_prime_pairs(): yield p   # strip out indexes
  43.  
  44. ps = primes()                               # 100k: 0.32s-9.8MB
  45. for n in xrange(1, 1000000): next(ps)       # 200k: 0.62s-9.8MB   n^0.95 !!
  46. print(next(ps))                             # 400k: 1.28s-9.8MB   n^1.05 !!!
  47.                                             # 1m:   3.11s-9.8MB   n^0.97 !!!   15485863
Success #stdin #stdout 3.1s 9800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
15485863
https://ideone.com/4Ld26g
Infinite generator using 2/3/5/7/11/13/17 wheel factorization incremental Sieve of Eratosthenes
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!