[Edu-sig] Generating prime numbers

[Edward Cherlin]

Your message text got stuck in an attachment, where I almost missed
it. I wonder what your mail system thinks it is doing? Comment below.

On Sat, Apr 4, 2009 at 12:48 PM, John Posner <jjposner at snet.net> wrote:
>

Sent today to python-list ...

Inspired by recent threads (and recalling my first message to Python
edu-sig), I did some Internet searching on producing prime numbers using
Python generators. Most algorithms I found don't go for the infinite,
contenting themselves with "list all the primes below a given number".

Here's a very Pythonic (IMHO) implementation that keeps going and going and
going ...:

from itertools import count
from math import sqrt

def prime_gen():
    """
    Generate all prime numbers
    """
    primes = []
    for n in count(2):
        if all(n%p for p in primes if p <= sqrt(n)):
            primes.append(n)
            yield n

The use of all() is particularly nifty (see
http://code.activestate.com/recipes/576640/). And so is the way in which the
list comprehension easily incorporates the sqrt(n) optimization.

Question: Is there a way to implement this algorithm using generator
expressions only -- no "yield" statements allowed?

I don't know about Python, but there are lazy evaluation languages
with streams that can handle something like

isprime=: {n.0 in [2:floor(sqrt(n))] | n}

isprime each [2:_]/[2:_]

where

floor is round down
| is remainder (mod)
each applies a function to each member of the argument
_ is positive infinity
/ (compress) returns elements of the right argument corresponding to
True values in the left argument

and we can get rid of the named function by simple substitution, thus

{n.0 in [2:floor(sqrt(n))] | n} [2:_]

2 passes as prime because [2:1] is empty, so it generates no 0 remainder.

Can you say that in Python?
-- 
Silent Thunder (默雷/धर्ममेघशब्दगर्ज/دھرممیگھشبدگر ج) is my name
And Children are my nation.
The Cosmos is my dwelling place, The Truth my destination.
http://earthtreasury.net/ (Edward Mokurai Cherlin)