fork(5) download
copy 
  1. from itertools import islice, count
  2. from fileinput import input
  3.                                          # ideone.com/aVndFM
  4. def postponed_sieve():                   # postponed sieve, by Will Ness      
  5.     yield 2; yield 3; yield 5; yield 7;  # original code David Eppstein, 
  6.     sieve = {}                           #   Alex Martelli, ActiveState Recipe 2002
  7.     ps = postponed_sieve()               # a separate base Primes Supply:
  8.     p = next(ps) and next(ps)            # (3) a Prime to add to dict
  9.     q = p*p                              # (9) its sQuare 
  10.     for c in count(9,2):                 # the Candidate
  11.         if c in sieve:               # c's a multiple of some base prime
  12.             s = sieve.pop(c)         #     i.e. a composite ; or
  13.         elif c < q:  
  14.              yield c                 # a prime
  15.              continue              
  16.         else:   # (c==q):            # or the next base prime's square:
  17.             s=count(q+2*p,2*p)       #    (9+6, by 6 : 15,21,27,33,...)
  18.             p=next(ps)               #    (5)
  19.             q=p*p                    #    (25)
  20.         for m in s:                  # the next multiple 
  21.             if m not in sieve:       # no duplicates
  22.                 break
  23.         sieve[m] = s                 # original test entry: ideone.com/WFv4f
  24.  
  25.  
  26.  
  27. def sieve():         # from code.activestate.com/recipes
  28.     yield 2          #                 /117119-sieve-of-eratosthenes
  29.     D = {}           # original code by
  30.     c = 3            #       David Eppstein, UC Irvine, 28 Feb 2002
  31.     while True:
  32.         s = D.pop(c, 0)
  33.         if s:
  34.             add(D,c + s,s)
  35.         else:
  36.             yield c
  37.             D[c*c] = 2*c
  38.         c += 2
  39.  
  40. def postponed_sieve1(): # postponed sieve, by Will Ness, ideone.com/WFv4f
  41.     yield 2            #  
  42.     D = {}             # see also:  stackoverflow.com/a/10733621/849891
  43.     c = 3                         # stackoverflow.com/a/8871918/849891
  44.     ps = (p for p in sieve())
  45.     p = ps.next() and ps.next()     # 3
  46.     q = p*p                         # 9
  47.     while True:
  48.         s = D.pop(c, 0)
  49.         if s:
  50.             add(D,c + s,s)
  51.         else:
  52.             if c < q:
  53.                 yield c
  54.             else:
  55.                 add(D,c + 2*p,2*p)
  56.                 p=ps.next()
  57.                 q=p*p
  58.         c += 2
  59.  
  60. def add(D,x,s):
  61.     while x in D: x += s
  62.     D[x] = s
  63.  
  64. for line in input():
  65.     n = int(line)
  66.     print(n)
  67.     print( list( islice( postponed_sieve(), n-1, n+1)))   
  68.     break
  69.  
  70. #                - base -              - postponed -
  71. # 
  72. # tested Sept 2012:
  73. #
  74. # 1500000                           11.65s-10.9   n^0.99
  75. # 1000000 11.14s-33.9   n^1.23       7.81s-10.9   n^1.01
  76. #  800000  8.46s-33.6   n^1.10       6.24s-10.9   n^1.11
  77. #  400000  3.96s-21.3   n^1.05       2.89s-10.9   n^1.02
  78. #  200000  1.91s-11.4   n^1.09       1.43s-10.9   n^1.01
  79. #  100000  0.90s-11.4MB              0.71s-10.9MB
  80. #
  81. #
  82. # tested in early 2012:
  83. # 
  84. # 1500000                          13.28s-4.7   n^1.09 
  85. # 1000000 10.83s-28.0  n^1.23       8.53s-4.7   n^1.08
  86. #  800000  8.23s-28.0  n^1.13       6.70s-4.7   n^1.09
  87. #  400000  3.76s-15.8  n^1.11       3.14s-4.7   n^1.07
  88. #  200000  1.74s-4.9MB              1.50s-4.7MB
Success #stdin #stdout 7.35s 8736KB
comments (?)
stdin
copy 
1000000
stdout
copy 
1000000
[15485863, 15485867]
https://ideone.com/aVndFM
primes generator, unique dict, postponed, on odds; cf V1rbwh (non-postponed, non-unique dict) ; 2-3-5-7 wheel at trR9OI ! original at WFv4f.
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!