Why should I switch to Python? - Infinity of Primes

[Harald Hanche-Olsen]

+ richard at cogsci.ed.ac.uk (Richard Tobin):

| In article <38EAC8C4.ADC25640 at cosc.canterbury.ac.nz>,
| Greg Ewing  <greg at cosc.canterbury.ac.nz> wrote:
| 
| >Um, no it doesn't - it constructs a number which is
| >*either* prime *or* divisible by some other prime bigger
| >than the one you started with.
| 
| It trivially gives you a procedure for finding a larger prime: you
| just find the factors of the constructed number (eg by trying all
| possible divisors), and if there are any then one will be a new prime,
| otherwise the constructed number is a new prime.

This thread is already much too long, but I can't resist pointing out
that the good old Erathostenes' sieve together with the ideas
introduced earlier in the thread provides a splendid constructive
proof:  Essentially, if the sieve has produced primes 2, 3, ..., p
then let q be one plus the product of 2, 3, ..., p.  Then the sieve
will produce a new prime no later than q.

Since this is a posted to a computer language group, after all, I
include my own simple implementation of the Sieve in Haskell:

primes :: [Integer]
primes = 2 : ([3..] `except` composites)

composites :: [Integer]
composites  = flatten (map (\ p -> [p*p, p*(p+1)..]) primes)

union :: [Integer] -> [Integer] -> [Integer]
xl@(x:xs) `union` yl@(y:ys) | x<y       = x : xs `union` yl
                            | x>y       = y : xl `union` ys
                            | otherwise = x : xs `union` ys

except :: [Integer] -> [Integer] -> [Integer]
xl@(x:xs) `except` yl@(y:ys) | x<y       = x : xs `except` yl
                             | x==y      = xs `except` ys
                             | otherwise = xl `except` ys

flatten :: [[Integer]] -> [Integer]
flatten ((x:xs):zz) = x : xs `union` (flatten zz)

I wonder if someone can come up with an equally immediate solution
(i.e., a straight translation from the mathematical formulation) in
python?

Indeed, I would be tempted to say that Haskell is better suited for
learning (some kinds of) mathematics than python.

but-I-wouldn't-dare-say-so-in-comp.lang.python-ly y'rs,
-- 
* Harald Hanche-Olsen     <URL:http://www.math.ntnu.no/~hanche/>
- "There arises from a bad and unapt formation of words
   a wonderful obstruction to the mind."  - Francis Bacon