Skip to content

Instantly share code, notes, and snippets.

@pnf
Last active December 19, 2015 08:19
Show Gist options
  • Save pnf/5924626 to your computer and use it in GitHub Desktop.
Save pnf/5924626 to your computer and use it in GitHub Desktop.
This is supposed to be a real sieve of eratosthenes, per http://www.cs.tufts.edu/~nr/comp150fp/archive/melissa-oneill/Sieve-JFP.pdf
(defn maintain-non-primes [non-primes]
"Remove first non-prime entry, and create new entries based on it"
(let [[n ps] (first non-primes)
xs (dissoc non-primes n)
new-non-primes (map (fn [p] [(+ n p) (cons p (xs (+ n p))) ]) ps)]
(into xs new-non-primes)))
(defn seive
([] (seive (sorted-map) 2))
([n] (take n (seive (sorted-map) 2)))
([non-primes n]
(if (= n (first (first non-primes))) ; did we hit the next non-prime?
(seive (maintain-non-primes non-primes) (+ n 1))
(cons n (lazy-seq (seive (assoc non-primes (* 2 n) [n]) (+ n 1)))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment