Skip to content

Instantly share code, notes, and snippets.

@Jach Jach/sieve.py
Created Feb 7, 2012

Embed
What would you like to do?
Incremental Sieve of Eratosthenes
'''
Python implementation of Haskell's
sieve xs = sieve' xs Map.empty
where
sieve' [] table = []
sieve' (x:xs) table =
case Map.lookup x table of
Nothing -> x : sieve' xs (Map.insert (x*x) [x] table)
Just facts -> sieve' xs (foldl reinsert (Map.delete x table) facts)
where
reinsert table prime = Map.insertWith (++) (x+prime) [prime] table
Found in "The Genuine Sieve of Eratosthenes"
'''
def sieve(inflist):
composites = {}
while True:
x = inflist.next()
if x not in composites:
yield x
composites[x*x] = [x]
else:
for prime in composites[x]:
composites.setdefault(x + prime, []).append(prime)
del composites[x]
def gennums(start):
n = start
while True:
yield n
n += 1
primes = sieve(gennums(2))
for i in xrange(20): # first 20 primes
print primes.next(),
# test:
primes = sieve(gennums(2))
for prime in [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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]:
assert prime == primes.next()
@indritselimi

This comment has been minimized.

Copy link

commented Apr 11, 2013

Great!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.