fork download
  1. from itertools import islice
  2.  
  3. def integers_from(n): # 2,3,4,...
  4. while True:
  5. yield n
  6. n += 1
  7.  
  8. def sieve(s):
  9. x = next(s)
  10. yield x
  11. ps = sieve( integers_from(2)) # independent primes supply
  12. p = next(ps)
  13. q = p*p ; print((p,q))
  14. while True:
  15. x = next(s)
  16. while x<q:
  17. yield x
  18. x = next(s)
  19. # here x == q
  20. s = filter(lambda y,p=p: y % p, s) # filter creation postponed
  21. p = next(ps) # until square of p seen in input
  22. q = p*p
  23.  
  24. print( list( islice( sieve( integers_from(2)), 19990, 20000) ))
  25.  
  26. # http://ideone.com/kYh7Di (non-postponed): this:
  27. # 390-400 0.11s 9.8MB 1000: 0.07s 9.6MB
  28. # 590-600 0.18s 10.2MB 10000: 0.34s 9.6MB 20k:0.80s-9.6M
  29. # 890-900 0.34s 10.5MB 100000: 6.96s 9.6MB n^1.3 !!! (optimal TD)
  30. # 990-1000 **run-time error: signal: 25 (SIGXFSZ)** 150000: 11.71s 10.3MB n^1.3
Success #stdin #stdout 0.79s 9568KB
stdin
Standard input is empty
stdout
(2, 4)
(2, 4)
(2, 4)
(2, 4)
(2, 4)
[224629, 224633, 224669, 224677, 224683, 224699, 224711, 224717, 224729, 224737]