Sunday, May 27, 2007

Sieve of Eratosthenes

#sieve.py
#
# The sieve of erasthosenes as an iterator
#
# eg.
#
# >>> from sieve import *
# >>> print(list(takeN(10, sieve()))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]


from itertools import count, takewhile, izip

def takeN(n, iter):
    for c, v in takewhile(lambda (c, v): c<=n, 
                        izip(count(1), iter)):
        yield v

def orF(fl, v):
    for f in fl:
        if f(v):
            return True
    return False

def sieve():
    isFactor = lambda p: lambda n: n%p==0
    l = []
    for i in count(2):
        if not orF(l, i):
            l = l + [isFactor(i)]
            yield i