Infinity sieve of Eratosthene. Ver.1

gistfile1.clj

(defn- diff-seq
  "Return a lazy seq of s1 except the element of s2.
both of s1 and s2 are monotone increase infinite sequences. "
  [s1 s2]
  (let [x1 (first s1), x2 (first s2)]
    (cond
     (= x1 x2) (recur (rest s1) (rest s2))
     (> x1 x2) (recur s1 (drop-while (partial > x1) s2))
     (< x1 x2) (let [[s11 s12] (split-with (partial > x2) s1)]
                 (lazy-cat s11 (diff-seq s12 s2))))))

(defn- muls
  "Return a lazy seq of multiples of n except the n itself."
  [n]
  (rest (iterate (partial + n) n)))

(defn- sieve
  "Return a lazy seq which removed the multiple of n from nums"
  [nums n]
  (diff-seq nums (muls n)))

(defn primes-sieve
  "Return a lazy sequence of prime numbers"
  ([]
     (primes-sieve (iterate inc 2) '(2)))
  ([nums prms-que]
     (let [p (first prms-que)
           nums (sieve nums p)
           [prms rest-nums] (split-with (partial > (* p p)) nums)
           prms-que (lazy-cat (rest prms-que) prms)]
       (lazy-cat prms (primes-sieve rest-nums prms-que)))))