fork(29) download
  1. # segmented sieve of eratosthenes
  2.  
  3. from math import sqrt
  4.  
  5. def primes(n):
  6. ps, sieve = [], [True] * (n)
  7. for p in range(2, n):
  8. if sieve[p]:
  9. ps.append(p)
  10. for i in range(p*p, n, p):
  11. sieve[i] = False
  12. return ps
  13.  
  14. def primesRange(lo, hi, delta):
  15. def qInit(p): return ((lo + p + 1) / -2) % p
  16. def qReset(p, q): return (q - delta) % p
  17. output, sieve = [], [True] * delta
  18. ps = primes(int(sqrt(hi)))[1:]
  19. qs = map(qInit, ps)
  20. while lo < hi:
  21. for i in range(0, delta):
  22. sieve[i] = True
  23. for p, q in zip(ps, qs):
  24. for i in range(q, delta, p):
  25. sieve[i] = False
  26. qs = map(qReset, ps, qs)
  27. for i, t in zip(range(0, delta), range(lo+1, hi, 2)):
  28. if sieve[i]: output.append(t)
  29. lo += (2 * delta)
  30. return output
  31.  
  32. print primesRange(100, 200, 10)
Success #stdin #stdout 0.08s 8840KB
stdin
Standard input is empty
stdout
[101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]