Re: [Tutor] primes

[Sean Perry]

Danny Yoo wrote:
Here is one that's traduced... er... adapted from material from the
classic textbook "Structure and Interpretation of Computer Programs":
######
from itertools import ifilter, count
def notDivisibleBy(n):
...     def f(x):
...         return x % n != 0
...     return f
...
def sieve(iterable):
...     nextPrime = iterable.next()
...     yield nextPrime
...     restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable))
...     for prime in restOfPrimes:
...         yield prime
...
primes = sieve(count(2))
primes.next()

which is cool, until you try to use it (-:
It dies at 999 primes due to an overloaded stack. Bummer. It is such a 
nifty implementation.

I modified this version to follow it better.
from itertools import ifilter, count
def notDivisibleBy(n):
    def f(x):
        return x % n != 0
    return f
def sieve(iterable):
    nextPrime = iterable.next()
    print 'x', nextPrime
    yield nextPrime
    restOfPrimes = sieve(ifilter(notDivisibleBy(nextPrime), iterable))
    for prime in restOfPrimes:
        print 'p', prime
        yield prime
primes = sieve(count(2))
current = primes.next()
count = 1
while current <= 20:
    print 'Prime:', current
    current = primes.next()
    count += 1
The output is (note this is each prime < 20):
x 2
Prime: 2
x 3
p 3
Prime: 3
x 5
p 5
p 5
Prime: 5
x 7
p 7
p 7
p 7
Prime: 7
x 11
p 11
p 11
p 11
p 11
Prime: 11
x 13
p 13
p 13
p 13
p 13
p 13
Prime: 13
x 17
p 17
p 17
p 17
p 17
p 17
p 17
Prime: 17
x 19
p 19
p 19
p 19
p 19
p 19
p 19
p 19
Prime: 19
x 23
p 23
p 23
p 23
p 23
p 23
p 23
p 23
p 23
Not exactly efficient.
_______________________________________________
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor