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)))