fork(15) download
copy 
  1. from itertools import islice
  2. from fileinput import input
  3.  
  4. def sieve():         # from code.activestate.com/recipes
  5.     yield 2          #                 /117119-sieve-of-eratosthenes
  6.     D = {}           # original code by
  7.     c = 3            #       David Eppstein, UC Irvine, 28 Feb 2002
  8.     while True:
  9.         s = D.pop(c, 0)
  10.         if s:
  11.             add(D,c + s,s)
  12.         else:
  13.             yield c
  14.             D[c*c] = 2*c
  15.         c += 2
  16.  
  17. def postponed_sieve(): # postponed sieve, by Will Ness, ideone.com/WFv4f
  18.     yield 2            #  
  19.     D = {}             # see also:  stackoverflow.com/a/10733621/849891
  20.     c = 3                         # stackoverflow.com/a/8871918/849891
  21.     ps = (p for p in sieve())
  22.     p = ps.next() and ps.next()     # 3
  23.     q = p*p                         # 9
  24.     while True:
  25.         s = D.pop(c, 0)
  26.         if s:
  27.             add(D,c + s,s)
  28.         else:
  29.             if c < q:
  30.                 yield c
  31.             else:
  32.                 add(D,c + 2*p,2*p)
  33.                 p=ps.next()
  34.                 q=p*p
  35.         c += 2
  36.  
  37. def add(D,x,s):
  38.     while x in D: x += s
  39.     D[x] = s
  40.  
  41. for line in input():
  42.     n = int(line)
  43.     print( list( islice( (p for p in postponed_sieve() ), n-1, n+1)))   
  44.     break
  45.  
  46. #                - base -              - postponed -
  47. # 
  48. # tested Sept 2012:
  49. #
  50. # 1500000                           11.65s-10.9   n^0.99
  51. # 1000000 11.14s-33.9   n^1.23       7.81s-10.9   n^1.01
  52. #  800000  8.46s-33.6   n^1.10       6.24s-10.9   n^1.11
  53. #  400000  3.96s-21.3   n^1.05       2.89s-10.9   n^1.02
  54. #  200000  1.91s-11.4   n^1.09       1.43s-10.9   n^1.01
  55. #  100000  0.90s-11.4MB              0.71s-10.9MB
  56. #
  57. #
  58. # tested in early 2012:
  59. # 
  60. # 1500000                          13.28s-4.7   n^1.09 
  61. # 1000000 10.83s-28.0  n^1.23       8.53s-4.7   n^1.08
  62. #  800000  8.23s-28.0  n^1.13       6.70s-4.7   n^1.09
  63. #  400000  3.76s-15.8  n^1.11       3.14s-4.7   n^1.07
  64. #  200000  1.74s-4.9MB              1.50s-4.7MB
Success #stdin #stdout 9.72s 7800KB
comments (?)
stdin
copy 
1270607
stdout
copy 
[19999999, 20000003]
https://ideone.com/WFv4f
primes generator, unique dict, postponed, on odds; cf V1rbwh (non-postponed, non-unique dict) ; 2-3-5-7 wheel at trR9OI !
language:
Python (cpython 2.7.16)
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!