Infinity sieve of Eratosthene. Ver.1

gistfile1.clj

(defn- diff-seq
  "Returns a lazy seq of numbers in s1 but not in s2.
  Both of s1 and s2 must be increasing monotonically and infinite sequence."
  [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 [[s1a s1b] (split-with (partial > x2) s1)]
                 (lazy-cat s1a (diff-seq s1b s2))))))

(defn- arithmetic-seq
  "Return a lazy arithmetic sequence"
  [start step]
  (iterate (partial + step) start))

(defn- prime-numbers*
  "Returns a lazy seq of prime numbers in nums."
  ([nums prms-que]
     (let [p (first prms-que)
           pp (* p p)
           sieved-nums (diff-seq nums (arithmetic-seq pp p))
           [prms rest-nums] (split-with (partial > pp) sieved-nums)
           prms-que (lazy-cat (rest prms-que) prms)]
       (lazy-cat prms (prime-numbers* rest-nums prms-que)))))

(defn prime-numbers
  "Return a lazy sequence of prime numbers."
  []
  (prime-numbers* (arithmetic-seq 2 1) '(2)))