Skip to content

Instantly share code, notes, and snippets.

@lypanov

lypanov/clojure: recursive sieve of eratosthenes

Created February 7, 2010 11:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lypanov/297384 to your computer and use it in GitHub Desktop.
Save lypanov/297384 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
clojure: recursive sieve of eratosthenes
(defn filter-multiples-of [p r]
(filter #(or (not= 0 (mod % p))
(= p %)) r))
(defn gen-primes
([n]
(gen-primes n 2 (range 2 n)))
([n p unfiltered]
(let [updated-unfiltered (filter-multiples-of p unfiltered)]
(when-first [next-p (filter #(> % p) updated-unfiltered)]
(if (> (* next-p next-p) n) updated-unfiltered
(recur n next-p updated-unfiltered))))))
(first (drop 10000 (gen-primes 200000)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment