Skip to content

Instantly share code, notes, and snippets.

@QQism
Created December 21, 2017 04:25
Show Gist options
  • Save QQism/f29634436a8cfeaffb2e98c116a98137 to your computer and use it in GitHub Desktop.
Save QQism/f29634436a8cfeaffb2e98c116a98137 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
(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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment