Eratosthenes's infinite sieve

prime_numbers.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."
  [s1 s2]
  (when-let [x1 (first s1)]
    (if-let [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))))
      s1)))

(defn- muls
  "Returns a lazy seq of multiples of n greater than n."
  [n]
  (drop 1 (iterate (partial + n) n)))

(defn- sieve
  "Returns a lazy seq of numbers in nums
  except multiples of n greater than n."
  [nums n]
  (diff-seq nums (muls n)))

(defn- prime-numbers*
  "Returns a lazy seq of prime numbers in nums."
  [nums prms-que]
  (when-let [nums (seq nums)]
    (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 (prime-numbers* rest-nums prms-que)))))

(defn prime-numbers
  "Returns a lazy seq of prime numbers."
  []
  (prime-numbers* (iterate inc 2) '(2)))