Why should I switch to Python? - Infinity of Primes

Harald Hanche-Olsen hanche at math.ntnu.no
Fri Apr 7 04:14:18 CEST 2000


+ "Tim Peters" <tim_one at email.msn.com>:

| Hmm.  Try out this one-liner Haskell defn, which is so pretty it *should*
| bring tears of joy to everyone's eyes <blink>:

Beautiful <sniff>, and almost certainly even easier to prove correct
than mine.  But it is also inefficient compared to my more clunky
implementation (statistics from hugs):

Primes> take 100 primes
[2,3,5,7,...,523,541]
(27698 reductions, 42791 cells)

which, by the way, is brought down by a factor of ten to
(2720 reductions, 4094 cells)
by employing a few more fairly obvious optimizations.

Primes> take 100 (sieve [2..]) where sieve (p:rest) = p : sieve [n | n <- rest, mod n p /= 0]
[2,3,5,7,...,523,541]
(394280 reductions, 573890 cells, 2 garbage collections)

beauty-hath-its-price-but-it's-worth-it-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



More information about the Python-list mailing list