fork download
copy 
  1. from itertools import *
  2.  
  3. def wsieve():       # wheel-sieve, by Will Ness.    ideone.com/mqO25A
  4.     wh11 = [ 2,4,2,4,6,2,6,4,2,4,6,6, 2,6,4,2,6,4,6,8,4,2,4,2,
  5.              4,8,6,4,6,2,4,6,2,6,6,4, 2,4,6,2,6,4,2,4,2,10,2,10]
  6.     cs = accumulate( chain( [11], cycle( wh11)))
  7.     yield( next( cs))  # cf. ideone.com/WFv4f
  8.     ps = wsieve()      #     codereview.stackexchange.com/q/92365/9064
  9.     p = next(ps)       # 11
  10.     psq = p*p          # 121
  11.     D = dict( zip( accumulate( chain( [0], wh11)), count(0)))   # start from
  12.     mults = {}
  13.     for c in cs:
  14.         if c in mults:                # a multiple of some prime:
  15.             wheel = mults.pop(c) 
  16.             for m in wheel: 
  17.                 if not m in mults:    # skip to the prime's next multiple
  18.                     break
  19.             mults[m] = wheel          # and put that back in
  20.         elif c < psq:              
  21.             yield c                   # a prime
  22.         else:                         # (c == psq) is the next prime's square  
  23.             # map (p*) (roll wh from p) = roll (wh*p) from (p*p)
  24.             x = [p*d for d in wh11]
  25.             i = D[ (p-11) % 210]
  26.             # accumulate( chain( [psq+x[i]], cycle( x[i+1:] + x[:i+1])))
  27.             for xi in (x[i:] + x[:i]):
  28.                 psq += xi
  29.                 wheel = count( psq, p*210)  # 48 counts for 1 accumulate:
  30.                 for m in wheel:             #              ... NOT worth it!
  31.                     if not m in mults: 
  32.                         break
  33.                 mults[m] = wheel
  34.             p = next(ps) ; psq = p*p 
  35.  
  36. def primes(): 
  37. 	yield from (2, 3, 5, 7)
  38. 	yield from wsieve()  
  39.  
  40. def tdprimes():
  41. 	yield from (2,3)
  42. 	for c in count(5,2):
  43. 		for d in count(3,2):
  44. 			if d*d > c:
  45. 				yield c
  46. 				break
  47. 			if (c % d) == 0:
  48. 				break
  49.  
  50. if True:                   
  51.     n = 2000000
  52.     print(n) 
  53.     print( list( islice(  primes() , n-1, n+1)))
Success #stdin #stdout 3.39s 26932KB
comments (?)
stdin
copy 
 ---  trR9OI ---- mqO25A  ----  sQC27a 
1m:  3.39s  --  3.45s 8.7M  -- 4.01s 8.8M
2m:  7.31s  --  7.50s 8.7M  -- 8.75s 8.8M
   ( n^1.11,     n^1.12,        n^1.13)
stdout
copy 
2000000
[32452843, 32452867]
https://ideone.com/sQC27a
forking ideone.com/mqO25A: == Indefinite UNROLLED Wheel Sieve of Eratosthenes == cf. codereview.stackexchange.com/q/92365/9064
language:
Python 3 (python  3.9.5)
created:
6 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!