michalmarczyk

(defn transient-incremental-sieve []
  (map first
       (iterate (fn [[previous crossouts]]
                  (loop [current (inc previous)
                         crossouts (transient crossouts)]
                    (if-let [witnesses (crossouts current)]
                      (recur (inc current)
                             (dissoc! (loop [cs crossouts
                                             ws witnesses]
                                        (if-let [w (first ws)]

michalmarczyk

# A priority queue-based, wheel-using incremental Sieve of Eratosthenes.
# See `The Genuine Sieve of Eratosthenes' by Melissa E. O'Neill
# (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf)
# for the Haskell incremental sieve which inspired this implementation
# (along with detailed analyses of performance of several Haskell
# sieves).
#
# Usage:
#   Sieve()         -> simple SoE
#   Sieve(Wheel(4)) -> SoE + a wheel based on 4 initial primes