Created
July 25, 2018 22:51
-
-
Save jpmonettas/44ea27fc0d573f5bd2e772c06bc5908c to your computer and use it in GitHub Desktop.
Clojure lazy primes
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
;; Addapted from python generator found at https://zach.se/project-euler-solutions/10/#python | |
(defn lazy-primes | |
"A lazy sequence that yields prime numbers using Eratosthenes Sieve impl." | |
([] (lazy-primes 2 {})) | |
;; n is the number we are checking for primality | |
;; facts maps composite integers to primes | |
([n facts] | |
(if (not (contains? facts n)) | |
(lazy-seq (cons n ;; yield since its not composite | |
(lazy-primes (inc n) | |
(assoc facts (* n n) [n])))) ;; and mark first multiple | |
(lazy-primes (inc n) (-> (reduce | |
(fn [r p] | |
(update r (+ p n) conj p)) | |
facts | |
(get facts n)) ;; move each witness to next multiple | |
(dissoc n)))))) ;; don't need it anymore |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment