Primes

unsorted — cgrand, 7 June 2008 @ 10 h 43 min

Last night on #clojure Lau_of_DK asked for a way to define the sequence of prime numbers.

Having helped Lou Franco in his effort to parallelize primes computation and solved the fourth question of Google Treasure Hunt using Clojure, I thought I knew pretty well how to produce primes in Clojure but I stumbled accross some Haskell code that was far smarter. Here it is, now ported to Clojure:

(def primes (lazy-cons 2 ((fn this[n]
  (let [potential-divisors (take-while #(<= (* % %) n) primes)]
    (if (some #(zero? (rem n %)) potential-divisors) 
      (recur (inc n))
      (lazy-cons n (this (inc n)))))) 3)))

It’s interesting to note that the seq is seeded with 1 and 2 because Clojure’s lazy seqs have a off by one evaluation (when one asks for the nth value, the nth+1 is computed — to know if the end of the seq is reached). No, no, no! I was plain wrong: if I need to seed with [1 2] 2 it’s because of the take-while whose predicate must return at least one false.

Update: In comments, Cale Gibbard points out that my definition of prime numbers is loose: 1 isn’t a prime. I fixed the code.

3 Comments »

  1. Very cool. I found some more discussion in a paper: The Genuine Sieve of Eratosthenes (pdf). I’ve put up an implementation in clojure-contrib in the file lazy-seqs.clj that borrows ideas from your blog post and the paper (and gives references to them). Performance averaged over the first 100,000 primes is about 206 microseconds per prime on a 2.16 GHz Core Duo.

    Comment by squeegee — 8 June 2008 @ 2 h 19 min
  2. @squeegee: thanks for the link to this interesting paper.

    Comment by Christophe Grand — 8 June 2008 @ 10 h 20 min
  3. Just thought I’d point out that 1 is by definition not a prime, since it has a multiplicative inverse (namely itself).

    The following small tweak to the code avoids this:

    (def primes (lazy-cat [2] ((fn this[n]
    (let [potential-divisors (take-while #(< = (* % %) n) primes)]
    (if (some #(zero? (rem n %)) (rest potential-divisors))
    (recur (+ n 2))
    (lazy-cons n (this (+ n 2)))))) 3)))

    Comment by Cale Gibbard — 8 June 2008 @ 21 h 41 min

RSS feed for comments on this post. TrackBack URI

Leave a comment

(c) 2017 Clojure and me | powered by WordPress with Barecity