A lazy primes function in Clojure using only addition and comparisons.

primes_via_addition.clj

(defn primes
  "Returns a lazy sequence of primes."
  []
  (cons 2
    (lazy-seq
     (let [local-primes (->> (primes)
                             (map (juxt identity #(apply + (repeat % %)))))]
       (->> (iterate #(+ % 2) 3)
            (remove (fn [n]
                      (->> local-primes
                           (take-while #(<= (second %) n))
                           (some (fn [[d]]
                                   (->> d
                                        (iterate #(+ % %))
                                        (take-while #(<= % n))
                                        (reverse)
                                        (reduce #(let [x (+ %1 %2)]
                                                   (if (> x n) %1 x))
                                                0)
                                        (= n))))))))))))

;; user> (time (nth (primes) 10000))
;; "Elapsed time: 7453.629671 msecs"                                                                     
;; 104743