Clojure code for finding prime numbers This is my Clojure code for finding prime numbers.

Note: this is an advanced version which starts eliminating from i*i with step i, instead of filtering all list against mod i == 0 (Sieve of Eratosthenes).

It has better asymptotic runtime: O(n log log n) instead of O(n log n) in typical examples of finding primes in Clojure.

What can be done better? Do I use some slow constructions? Can I make it more concise? Gain more performance? Format it better?

(defn primes [n]
  (let [mark (fn [i di v]
               (if (&lt;= i (count v))
                 (recur (+ i di) di (assoc v (dec i) di))
                 v))
        step (fn [i ps v]
               (if (&lt;= i (count v))
                 (if (= (v (dec i)) 1)
                   (recur (inc i) (conj ps i) (mark (* i i) i v))
                   (recur (inc i) ps v))
                 ps))]
(-&gt;&gt; (repeat 1) (take n) vec (step 2 []))))

(defn -main
  [&amp; args]
  (println (primes 50)))
(non-Clojure-specific) Gain performance, sure. Use packed array of odds, where index i represents value 2i+1. Then you don't have to deal with evens, which are all non-prime a priori (except the 2 of course). Then you can increment by 2*p for a prime p to find its odd multiples twice faster.

For a non-marked index i, the prime p is p = 2*i+1, its square is p*p = (2i+1)(2i+1) = 4i^2 + 4i + 1 and its index is (p*p-1)/2 = 2i^2 + 2i = 2i(i+1) = (p-1)(i+1). For the value increment of 2*p, the index increment on 2x-packed array is di = p = 2i+1.