fork(6) download
  1. from itertools import islice
  2. from fileinput import input
  3.  
  4. def sieve(): # from http://code.activestate.com/
  5. yield 2 # recipes/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 http://ideone.com/WFv4f
  18. yield 2 #
  19. D = {} # see also: http://stackoverflow.com/a/10733621/849891
  20. c = 3 # http://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.41s 7848KB
stdin
1270607
stdout
[19999999, 20000003]