transient incremental sieves

transient-incremental-sieves.clj

(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)]
                                          (if-let [ps (cs (+ w current))]
                                            (recur (assoc! cs (+ w current) (conj ps w))
                                                   (rest ws))
                                            (recur (assoc! cs (+ w current) #{w})
                                                   (rest ws)))
                                          cs))
                                      current))
                      [current (persistent! (assoc! crossouts (* current current) #{current}))])))
                [2 {4 #{2}}])))

(defn odd-transient-incremental-sieve []
  (cons 2
        (map first
             (iterate (fn [[previous crossouts]]
                        (loop [current (+ previous 2)
                               crossouts (transient crossouts)]
                          (if-let [witnesses (crossouts current)]
                            (recur (+ current 2)
                                   (dissoc! (loop [cs crossouts
                                                   ws witnesses]
                                              (if-let [w (first ws)]
                                                (if-let [ps (cs (+ (* 2 w) current))]
                                                  (recur (assoc! cs (+ (* 2 w) current) (conj ps w))
                                                         (rest ws))
                                                  (recur (assoc! cs (+ (* 2 w) current) #{w})
                                                         (rest ws)))
                                                cs))
                                            current))
                            [current (persistent! (assoc! crossouts (* current current) #{current}))])))
                      [3 {9 #{3}}]))))