2

Possible Duplicate:
Recursive function causing a stack overflow

Working through the example lazy-seq here.

(defn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                             (rest s))))))

If I try to generate more than a couple of thousand primes or so, I get an OutOfMemoryError. Based on my research (but I am very new to clojure) I suspect this may be a problem of the class "hold onto head" but cannot figure out why that would be or how it might be remedied. How can this function be altered so as not to run out of memory when generating larger numbers of primes?

Community
  • 1
  • 1
richguy
  • 23
  • 2
  • Also asked here http://stackoverflow.com/questions/2980587/clojure-tail-recursive-sieve-of-eratosthenes, answered here http://stackoverflow.com/questions/2946764/recursive-function-causing-a-stack-overflow. – A. Webb Jan 12 '13 at 21:30
  • Thank you for pointing to this, this answers my question, I thought I had searched sufficiently, apparently not. – richguy Jan 12 '13 at 22:15
  • Although, after working through it, it doesn't actually seem to solve my issue. – richguy Jan 12 '13 at 22:30
  • There is this link http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/ which has a efficient lazy prime definition. – A. Webb Jan 13 '13 at 00:55
  • That cgrand code is beautiful, thanks for the pointer. – richguy Jan 13 '13 at 02:20

2 Answers2

2

You can use version without creating lazy sequence. It works faster and cheaper:

 (defn sieve* [res s]
      (if (empty? s)
        res
        (recur (conj res (first s))
               (filter #(not= 0 (mod % (first s)))
                       (rest s)))))

(defn sieve [n]
  (sieve* [] (range 2 n)))

(sieve 10000)
=> [2 3 5 7 11 13 17 ... 9941 9949 9967 9973]

And here is more efficient version:

(defn sieve* [res n maxn]
  (if (> n maxn)
    res
    (if (some #(= 0 (mod n %))
              (take (round (sqrt (count res))) res))
      (recur res (inc n) maxn)
      (recur (conj res n) (inc n) maxn))))

(defn sieve [n]
  (sieve* [] 2 n))

(last (sieve 1000000))
=> 999983

Update. Pretty fast/cheap lazy version

(defn primes-seq* [primes]
  (let [last-prime (last primes)]
    (cons last-prime
          (lazy-seq
           (primes-seq*
            (conj primes
                  (first (let [compare-primes
                               (take (round (sqrt (count primes)))
                                     primes)]
                           (drop-while (fn [n]
                                         (some #(= 0 (mod n %))
                                               compare-primes))
                                       (iterate inc (inc last-prime)))))))))))


(def primes-seq (primes-seq* [2]))

(last (take 50000 primes-seq))
=> 611953
mobyte
  • 3,752
  • 1
  • 18
  • 16
1

The given algorithm works by "remembering" all the previous primes, so you are going to blow the stack if you keep going long enough.

The following may be less efficient but will not use up memory (adapted from my 4clojure solution to #116):

(defn prime-seq []
  (letfn [(is-prime [x]
            (not (some #(= (rem x %) 0) (range 2 x))))]
    (filter is-prime (range))))

(take 20 (prime-seq))
;=> (0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61)
(nth (prime-seq) 10000)
;=> 104723
JohnJ
  • 4,753
  • 2
  • 28
  • 40