fork(5) download
  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
stdin
1m:  3.39s-8.7M
2m:  7.31s-8.7M
stdout
1000000
[15485863, 15485867]