Sieve of Eratosthenes

sieve-of-eratosthenes.clj

(defn mark [xs idx]
  "Iterate over the xs with each j step of (idx * idx + (j * idx))
   For each element of step, mark them false (a.k.a not a prime number)"
  (loop [arr xs
         j 0]
    (let [step (+ (* idx idx ) (* j idx))]
      (if (< step (count arr))
        (recur (assoc arr step false) (inc j))
        arr))))

(defn sieve [maximum]
  "Create a xs vector of true values having the length of maximum
   Iterate over the xs and run sieve if the element is true
   Vector is used instead of list because it gives O(1) for accessing a random element"
  (loop [xs (vec (repeat maximum true))
         idx 2]
    (if (< idx (count xs))
      (if (nth xs idx)
        (recur (mark xs idx) (inc idx))
        (recur xs (inc idx)))
      xs)))

(defn run-sieve [maximum]
  "Normalize the result after sieving:
   - Return the list of indexes having true values, for others, set them as 0
   - Remove element of 0 and drop index of 1 (1 is not a prime number)"
  (->> (sieve maximum)
       (map-indexed (fn [k v] (if v k 0)))
       (filter #(not= % 0))
       (drop 1)))

;; Return prime numbers less than 100
(run-sieve 100)
;;(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)