Skip to content

Instantly share code, notes, and snippets.

@lotabout
Last active March 7, 2022 15:58
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lotabout/6a8b1f66d6db84d33796d39c73399d7c to your computer and use it in GitHub Desktop.
Save lotabout/6a8b1f66d6db84d33796d39c73399d7c to your computer and use it in GitHub Desktop.
Infinite sequence of prime numbers in Clojure.
; Sieve of Eratosthenes
; Checkout https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
(def primes
(concat
[2]
(lazy-seq
(let [prime-inner
(fn prime-inner [x table]
(if (table x)
(prime-inner (inc x)
(reduce #(update % (+ x %2) conj %2)
(dissoc table x)
(table x)))
(lazy-seq (cons x (prime-inner (inc x) (assoc table (* x x) [x]))))))]
(prime-inner 3 {4 [2]})))))
(take 10 primes)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment