tag:blogger.com,1999:blog-5533633605592253922.post3703700257329911819..comments2009-09-26T23:52:34.853+02:00Comments on Clojure and me: PrimesChristophe Grandhttp://www.blogger.com/profile/14317541771600107537noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5533633605592253922.post-43563491457646180872008-06-08T21:41:00.000+02:002008-06-08T21:41:00.000+02:00Just thought I'd point out that 1 is by definition...Just thought I'd point out that 1 is by definition not a prime, since it has a multiplicative inverse (namely itself).<BR/><BR/>The following small tweak to the code avoids this:<BR/><BR/>(def primes (lazy-cat [2] ((fn this[n]<BR/> (let [potential-divisors (take-while #(<= (* % %) n) primes)]<BR/> (if (some #(zero? (rem n %)) (rest potential-divisors)) <BR/> (recur (+ n 2))<BR/> (lazy-cons n (this (+ n 2)))))) 3)))Cale Gibbardhttps://www.blogger.com/profile/02239068589033148700noreply@blogger.comtag:blogger.com,1999:blog-5533633605592253922.post-64883376736103267752008-06-08T10:20:00.000+02:002008-06-08T10:20:00.000+02:00@squeegee: thanks for the link to this interesting...@squeegee: thanks for the link to this interesting paper.Christophe Grandhttps://www.blogger.com/profile/14317541771600107537noreply@blogger.comtag:blogger.com,1999:blog-5533633605592253922.post-22456565267119133162008-06-08T02:19:00.000+02:002008-06-08T02:19:00.000+02:00Very cool. I found some more discussion in a pape...Very cool. I found some more discussion in a paper: <A HREF="http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf" REL="nofollow">The Genuine Sieve of Eratosthenes (pdf)</A>. I've put up an implementation in clojure-contrib in the file <A HREF="http://clojure-contrib.svn.sourceforge.net/viewvc/clojure-contrib/trunk/lazy-seqs.clj?view=markup" REL="nofollow">lazy-seqs.clj</A> 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.scgilardihttps://www.blogger.com/profile/02744110455629077693noreply@blogger.com