[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.