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 (<= i (count v))
(recur (+ i di) di (assoc v (dec i) di))
v))
step (fn [i ps v]
(if (<= 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))]
(->> (repeat 1) (take n) vec (step 2 []))))
(defn -main
[& args]
(println (primes 50)))
n log (log n)only if(assoc v (dec i) di)is O(1). – Will Ness Jul 25 '13 at 7:15