fork(4) download
  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
stdin
1000000
stdout
1000000
[15485863, 15485867]