CODEWITHSUNDEEP
pythonclojure
Roskoto
Roskoto

Reputation: 1750

Clojure prime numbers lazy sequence

What is the Clojure equivalent (for the exact algorithm) of the following Python code?

from itertools import count
from math import sqrt

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

Upvotes: 8

Views: 3454

Answers (3)

Thumbnail
Thumbnail

Reputation: 13473

Here is the algorithm in fairly idiomatic Clojure. I've tried to keep the names the same so that you can see how this code corresponds.

(def all? (partial every? identity))

(defn prime-gen []
  (let [unfold
        (iterate
          (fn step [[primes n]]
            (if (all?
                  (for [p primes :when (<= p (Math/sqrt n))]
                    (not= 0 (mod n p))))
              [(conj primes n) (inc n)]
              (recur [primes (inc n)])))
          [[] 2])]
    (map (comp peek first) (rest unfold))))

Every iteration of step

  • appends the next prime to the first component of its argument and
  • hands on the next candidate prime in the second component.

The last line picks out the appended primes from the iterations.

It works:

(take 11 (prime-gen))
=> (2 3 5 7 11 13 17 19 23 29 31)

We can also see some inefficiency: The :when (<= p (Math/sqrt n) clause (and its Python equivalent if p <= sqrt(n)) are useless. We still go through all the discovered primes instead of stopping when they get too big to be possible factors. To mend this,

  • in Clojure, we replace the :when with a :while;
  • in Python, I think we wrap primes in a takewhile instead of following it with an if (untested).

Even so, the algorithm is slow. For something faster, see lazy-primes3 from Christophe Grand's blog on the subject.

Upvotes: 0

SaltyEgg
SaltyEgg

Reputation: 1558

This version is much faster than @Brian Carper's

(def prime-gen
  (let [primes (atom [2N])]
    (iterate
      #(let [ps @primes]
         (loop [n (inc %)]
           (if (loop [i 0]
                 (let [p (nth ps i)]
                   (cond
                     (< n (* p p)) true
                     (zero? (mod n p)) false
                     :else (recur (inc i)))))
             (do (swap! primes conj n) n)
             (recur (inc n)))))
      (first @primes))))

Upvotes: 0

Brian Carper
Brian Carper

Reputation: 72926

This is as Pythonish as I can make it:

(def prime-gen
     (let [primes (atom [])]
       (for [n (iterate inc 2)
             :when (not-any? #(zero? (rem n %))
                             (filter #(<= % (Math/sqrt n)) 
                                     @primes))]
         (do (swap! primes conj n)
             n))))

(take 10 prime-gen)  ; => (2 3 5 7 11 13 17 19 23 29)

Clojure doesn't consider the integer 0 to be boolean false. It took me a few minutes to figure out that your Python code was taking advantage of this.

Here are some other prime number algorithms in Clojure. There's also a prime number implementation in clojure.contrib.lazy-seqs.

Upvotes: 11

Related Questions