Velocity Reviews > sieve.py

# sieve.py

Lawrence D'Oliveiro
Guest
Posts: n/a

 09-30-2005
As an exercise in learning about Python and its iterators, here's a
ridiculously recursive implementation of the Sieve of Eratosthenes,
based on the well-known massively-parallel implementation. On my Linux
box, it gets up to 3557 (about 500 levels deep) before dying from a
stack overflow.

#+
# A Python implementation of the Sieve of Eratosthenes
# using recursive iterators. Unfortunately this doesn't get
# very far before it overflows the recursion stack.
#
# Created 2005 September 30 by Lawrence D'Oliveiro
<(E-Mail Removed)_zealand>.
#-

class IntegersFrom2 :
"""enumerates the integers in sequence, starting from 2."""
def __init__(self) :
self.i = 1
def __iter__(self) :
return self
def next(self) :
self.i += 1
return self.i

class NotDivisible :
"""enumerates the integers yielded by Iterator, filtering out those
divisible by Divisor."""
def __init__(self, Iterator, Divisor) :
self.Iterator = Iterator
self.Divisor = Divisor
def __iter__(self) :
return self
def next(self) :
while 1 :
i = self.Iterator.next()
if (i % self.Divisor != 0) :
break
return i

class Sieve :
"""iterates over the primes. Call as "Sieve(IntegersFrom2())"
to initialize; recursively instantiates itself every time it
hits a new prime, to filter out multiples of that prime."""

def __init__(self, IntSource) :
self.IntSource = iter(IntSource)
# first integer in sequence is always prime
self.Divisor = self.IntSource.next()

def __iter__(self) :
self.next = self.FirstIter
return self

def FirstIter(self) :
# yields self.Divisor as the first integer in the
# sequence, and recursively instantiates the Sieve
# class to filter subsequent multiples of self.Divisor.
self.IntSource = \
iter(Sieve(NotDivisible(self.IntSource, self.Divisor)))
self.next = self.SubsequentIter
return self.Divisor

def SubsequentIter(self) :
# returns the rest of the sequence filtered through
# the sub-Sieve.
return self.IntSource.next()

for i in iter(Sieve(IntegersFrom2())) :
print i