Skip to content

Instantly share code, notes, and snippets.

@jpmonettas
Created July 25, 2018 22:51
Show Gist options
  • Save jpmonettas/44ea27fc0d573f5bd2e772c06bc5908c to your computer and use it in GitHub Desktop.
Save jpmonettas/44ea27fc0d573f5bd2e772c06bc5908c to your computer and use it in GitHub Desktop.
Clojure lazy primes
;; 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