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.     for p in [2,3,5,7]: yield p                 # base wheel primes
  5.     gaps1 = [ 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8 ]
  6.     gaps = gaps1 + [ 6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 ] # wheel2357
  7.     def wheel_prime_pairs():
  8.         yield (11,0); bps = wheel_prime_pairs() # additional primes supply
  9.         p, pi = next(bps); q = p * p            # adv to get 11 sqr'd is 121 as next square to put
  10.         sieve = {}; n = 13; ni = 1              #   into sieve dict; init cndidate, wheel ndx
  11.         while True:
  12.             if n not in sieve:                  # is not a multiple of previously recorded primes
  13.                 if n < q: yield (n, ni)         # n is prime with wheel modulo index
  14.                 else:
  15.                     npi = pi + 1                # advance wheel index
  16.                     if npi > 47: npi = 0
  17.                     sieve[q + p * gaps[pi]] = (p, npi) # n == p * p: put next cull position on wheel
  18.                     p, pi = next(bps); q = p * p  # advance next prime and prime square to put
  19.             else:
  20.                 s, si = sieve.pop(n)
  21.                 nxt = n + s * gaps[si]          # move current cull position up the wheel
  22.                 si = si + 1                     # advance wheel index
  23.                 if si > 47: si = 0
  24.                 while nxt in sieve:             # ensure each entry is unique by wheel
  25.                     nxt += s * gaps[si]
  26.                     si = si + 1                 # advance wheel index
  27.                     if si > 47: si = 0
  28.                 sieve[nxt] = (s, si)            # next non-marked multiple of a prime
  29.             nni = ni + 1                        # advance wheel index
  30.             if nni > 47: nni = 0
  31.             n += gaps[ni]; ni = nni             # advance on the wheel
  32.     for p, pi in wheel_prime_pairs(): yield p   # strip out indexes
  33.  
  34. ps = primes()                               # 100k: 0.33s-7.9MB
  35. for n in xrange(1, 1000000): next(ps)       # 200k: 0.74s-7.9MB   n^1.22 !!
  36. print(next(ps))                             # 400k: 1.54s-7.9MB   n^1.06 !!!
  37.                                             # 1m:   4.12s-7.9MB   n^1.07 !!!   15485863
Success #stdin #stdout 3.97s 7896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
15485863
https://ideone.com/LFaRnT
Infinite generator using 2/3/5/7 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!