# Clojure Sieve Of Eratosthenes

## Apr 24, 2016 09:03 · 305 words · 2 minute read clojure functional programming

I was recently watching a video on Haskell that was showing how you would write a functional form of the Sieve of Eratosthenes. I personally love this algorithm and was interested in what it looked like in Clojure. So I wrote this:

``````(defn sieve [number xs]
(if (= 0 number)
xs
(conj (sieve (dec number)
(filter #(not= 0 (mod % (first xs))) (rest xs)))
(first xs))))
``````

This works, but Clojure doesn’t have tail call optimization (TCO) by default which means you can get a stack StackOverflowError. So I decided to rewrite it to use the loop and recur construct to remove the StackOverflowError. It looks like this:

``````(defn sieve [number xs]
(loop [number number
xs xs
return-value nil]
(if (= 0 number)
return-value
(recur (dec number)
(filter #(not= 0 (mod % (first xs))) (rest xs))
(conj return-value (first xs))))))
``````

Which can be called like this:

``````(sieve 1000 (iterate inc 2))
``````

I like this implementation, but I wanted to see what would happen when I pushed it towards it’s limit. So I went ahead and I ran:

``````(sieve 10000 (iterate inc 2))
``````

At which point I promptly got;

StackOverflowError clojure.lang.Numbers.inc (Numbers.java:112)

A little sad and perplexed, it wasn’t immediately obvious to me why I was getting a stack overflow. Well it turns out that recur can’t use TCO on lazy lists. In particular;

``````(filter #(not= 0 (mod % (first xs))) (rest xs))
``````

Doesn’t work, but if we change the implementation to:

``````(defn sieve [number xs]
(loop [number number
xs xs
return-value nil]
(if (= 0 number)
return-value
(recur (dec number)
(doall (filter #(not= 0 (mod % (first xs))) (rest xs)))
(conj return-value (first xs))))))

``````

and we call it as

``````(sieve 10000 (range 2 1000000))
``````

While it takes some time, the above does come back without a StackOverflowError, but at the cost of losing the lazy evaluation.

tweet Share