Skip to content

Instantly share code, notes, and snippets.

@kannangce
Last active April 11, 2019 12:48
Show Gist options
  • Save kannangce/d1ef4008f2310ce809437ec8686de877 to your computer and use it in GitHub Desktop.
Save kannangce/d1ef4008f2310ce809437ec8686de877 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes in clojure
(defn multiple?
"Check if the number-to-check is a multiple of number."
[number-to-check number]
(= 0 (mod number-to-check number)))
(defn sieve-of-eratosthenes
"For the number ranging from 2 to the given number 'upto'(inclusive),
filters out all the numbers that are not prime and
return the prime numbers."
[upto]
; Remove if 1 is present in the first
(def all-but-one (range 2 (inc upto)))
(def limit (Math/sqrt upto))
(loop [curr 2 processed [] remaining all-but-one]
(if (> curr limit)
(concat processed remaining)
(recur (second remaining) ; Move the next number
(conj processed curr) ; Add the current to the processed
(filter #(not (multiple? % curr)) remaining))))) ; Filter out everything that are multiples
; Verification
; user=> (sieve-of-eratosthenes (range 1 20))
; (2 3 5 7 11 13 17 19)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment