Skip to content

Instantly share code, notes, and snippets.

@hvr
Created May 24, 2010 11:50
Show Gist options
  • Save hvr/411780 to your computer and use it in GitHub Desktop.
Save hvr/411780 to your computer and use it in GitHub Desktop.
Python prime number generator using "Sieve of Eratosthenes" algorithm
def primes(limit):
"""
generate lazy (finite) sequence of primes below limit
>>> list(primes(100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sum(primes(1000*1000))
37550402023
"""
sieve = [False]*limit
for j in xrange(2, limit):
if sieve[j]: continue
yield j # got new prime
if j*j > limit: continue # optimization
for i in xrange(j, limit, j):
sieve[i] = True # fastest to just update even if redundant
if __name__ == '__main__':
import doctest
doctest.testmod()
from timeit import timeit
print("starting timing tests...")
print(timeit("sum(primes(100*1000))", "from __main__ import primes", number=100)/100)
print(timeit("sum(primes(1000*1000))", "from __main__ import primes", number=10)/10)
print(timeit("sum(primes(10*1000*1000))", "from __main__ import primes", number=3)/3)
print("done with timing tests...")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment