This is supposed to be a real sieve of eratosthenes, per http://www.cs.tufts.edu/~nr/comp150fp/archive/melissa-oneill/Sieve-JFP.pdf

lazysieve.clj

(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)))))))