[Tutor] primes

[Danny Yoo]

On Thu, 17 Mar 2005, Gregor Lingl wrote:

> Hi!
> Who knows a more concise or equally concise but more efficient
> expression, which returns the same result as
>
> [x for x in range(2,100) if not [y for y in range(2,x) if x%y==0]]


Hi Gregor,

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()
2
>>> primes.next()
3
>>> primes.next()
5
>>> primes.next()
7
>>> primes.next()
11
>>> primes.next()
13
>>> primes.next()
17
>>> primes.next()
19
>>> primes.next()
23
######

The neat thing about this code is that it produces an infinite iterator of
prime numbers.  The original code in Scheme is itself quite concise and
quite nice.  It is described here:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#call_footnote_Temp_455


Best of wishes to you!