Skip to content

Instantly share code, notes, and snippets.

@retzkek
Last active January 2, 2016 10:18
Show Gist options
  • Save retzkek/8288618 to your computer and use it in GitHub Desktop.
Save retzkek/8288618 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes in Clojure (first attempt, undoubtedly can be improved)
(ns kmr.primes
(:use clojure.set))
(defn eratos
"Compute all primes below n using Sieve of Eratosthenes."
[n]
(loop [i 2
sieve (set (range 2 (inc n)))]
(if (> (* i i) n)
sieve
(recur (first (drop-while #(not (contains? sieve %)) (range (inc i) n)))
(difference sieve (set (range (+ i i) (inc n) i)))))))
(= (sort (eratos 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