Skip to content

Instantly share code, notes, and snippets.

@metric-space
Last active September 1, 2016 03:51
Show Gist options
  • Save metric-space/32189a6b878f93e64805f75305bc94df to your computer and use it in GitHub Desktop.
Save metric-space/32189a6b878f93e64805f75305bc94df to your computer and use it in GitHub Desktop.
sieve of eratosthenes in clojure
(defn generate-primes-till [x]
;; sieve of eratosthenes
(let [coll (take-while #(< % x) (iterate (partial + 2) 3))
sq (fn [x] (* x x))
not-a-multiple (fn [x a] (or (= a x) (> (mod a x) 0)))
steps (take-while #( < (sq %) x) coll)]
(cons 2 (reduce (fn [a,x] (filter #(not-a-multiple x %) a))
coll steps))))
(println (generate-primes-till 1000 ))
;; steps
;; 1. generate list of infinite odd numbers less than input
;; 2. generate a sublist of above list that have their squares less than input
;; 3. reduce over the sublist and eliminate multiples (excuding the number itself
;; example -> take off multiples of 3 but not three) in the main list
;; 4. append 2 to the output
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment