fork(8) download
copy 
  1. from itertools import *
  2.  
  3. def wsieve():       # wheel-sieve, by Will Ness.   ideone.com/trR9OI
  4.     yield 11        # cf. ideone.com/WFv4f
  5.     mults = {}      #     codereview.stackexchange.com/q/92365/9064
  6.     ps = wsieve()   
  7.     p = next(ps)       # 11
  8.     psq = p*p          # 121
  9.     D = dict( zip( accumulate( [0,       # where to start
  10.                  2,4,2,4,6,2,6,4,2,4,6,6, 2,6,4,2,6,4,6,8,4,2,4,2,
  11.                  4,8,6,4,6,2,4,6,2,6,6,4, 2,4,6,2,6,4,2,4,2,10,2,10] ),
  12.                    count(0)))
  13.     for c in accumulate( chain( [13], cycle( 
  14.                 [  4,2,4,6,2,6,4,2,4,6,6, 2,6,4,2,6,4,6,8,4,2,4,2,
  15.                  4,8,6,4,6,2,4,6,2,6,6,4, 2,4,6,2,6,4,2,4,2,10,2,10,2] ))):
  16.         if c in mults:
  17.             wheel = mults.pop(c)  
  18.         elif c < psq:              
  19.             yield c ; continue   
  20.         else:          # (c==psq)   
  21.             p2=p*2   ;   p6=p*6   ;  p10=p*10 # map (p*) (roll wh from p) =
  22.             p4=p*4   ;   p8=p*8               #  = roll (wh*p) from p*p
  23.             wheel = accumulate( chain( [p*p], islice( cycle( 
  24.                           [p2,p4,p2,p4,p6,p2,p6,p4,p2,p4,p6,p6,
  25.                            p2,p6,p4,p2,p6,p4,p6,p8,p4,p2,p4,p2,
  26.                            p4,p8,p6,p4,p6,p2,p4,p6,p2,p6,p6,p4,
  27.                            p2,p4,p6,p2,p6,p4,p2,p4,p2,p10,p2,p10] ),
  28.                           D[ (p-11) % 210 ], None )))
  29.             p = next(ps) ; psq = p*p ; next(wheel)   # p*p
  30.         for m in wheel: 
  31.             if not m in mults: 
  32.                 break
  33.         mults[m] = wheel
  34.  
  35. def primes(): 
  36. 	yield from (2, 3, 5, 7)
  37. 	yield from wsieve()  
  38.  
  39. if True:                   
  40.     n = 1000000  # ! 1.5x speedup vs nw1BQn: 1M 5.1/3.4  2M 10.88/7.2
  41.     print(n) 
  42.     print( list( islice( (p for p in primes() ), n-1, n+1)))
Success #stdin #stdout 3.39s 8736KB
comments (?)
stdin
copy 
1m:  3.39s-8.7M
2m:  7.31s-8.7M
stdout
copy 
1000000
[15485863, 15485867]
https://ideone.com/trR9OI
Indefinite Wheel Sieve of Eratosthenes == cf. aVndFM, nw1BQn == codereview.stackexchange.com/q/92365/9064 -- ideone.com/mqO25A is a shorter code, 2% slower.
language:
Python 3 (python  3.9.5)
created:
8 years ago
visibility:
public

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!