Last active
November 2, 2020 18:53
-
-
Save wedesoft/879f29a882c086a0b38c078da2803d70 to your computer and use it in GitHub Desktop.
Prime number sieve of Eratosthenes in Clojure
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
; 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