Clojure - tail recursive sieve of Eratosthenes
- by Konrad Garus
I have this implementation of the sieve of Eratosthenes in Clojure:
(defn sieve [n]
(loop [last-tried 2 sift (range 2 (inc n))]
(if
(or (nil? last-tried) (> last-tried n))
sift
(let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
(let [next-to-try (first (filter #(> % last-tried) filtered))]
(recur next-to-try filtered))))))
For larger n (like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?
