Skip to content

Instantly share code, notes, and snippets.

@wedesoft
Last active November 2, 2020 18:53
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 wedesoft/879f29a882c086a0b38c078da2803d70 to your computer and use it in GitHub Desktop.
Save wedesoft/879f29a882c086a0b38c078da2803d70 to your computer and use it in GitHub Desktop.
Prime number sieve of Eratosthenes in Clojure
; This one is really nice and compact but it quickly runs out of stack space:
(defn primes [i] (cons i (lazy-seq (filter #(not (zero? (mod % i))) (primes (inc i))))))
(take 100 (primes 2))
; (2 3 5 7 ...)
(take 1000 (primes 2))
; Error printing return value (StackOverflowError) at user/primes (NO_SOURCE_FILE:1).
; This one is slightly less elegant but works for large numbers:
(defn primes [i p]
(if (some #(zero? (mod i %)) p)
(recur (inc i) p)
(cons i (lazy-seq (primes (inc i) (conj p i))))))
(take 1000 (primes 2 []))
; (2 3 5 7 ...)
; modified from https://stackoverflow.com/a/53231994/382784
(def primes
(lazy-seq
(filter (fn [i] (not-any? #(zero? (rem i %))
(take-while #(<= (* % %) i) primes)))
(drop 2 (range)))))
(take 1000 primes)
; less compressed version
(def primes
(lazy-seq
(filter (fn [i] (not-any? (fn [p] (zero? (rem i p)))
(take-while (fn [p] (<= (* p p) i)) primes)))
(drop 2 (range)))))
(take 1000 primes)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment