Naïve Prime Factorization in Clojure Pt. 2
All that the lazily-find-prime-factors function needs is the (primes) sequence. You just keep trying each in turn. Your smallest-factor-of drops the failed factors, but forgets what it has done, so you have to do it again for the recursive call. 

And I'd rename your is-factor-of? function:

=&gt; (is-factor-of? 4 2)
true
=&gt; (is-factor-of? 2 4)
false


... reads wrongly. I've called it divides-by?.

I end up with ... 

(defn lazily-find-prime-factors [n]
  (letfn [(rec [remaining remaining-primes]
            (when (&gt; remaining 1)
              (let [rp (drop-while #(not (divides-by? remaining %)) remaining-primes)
                    small-prime (first rp)]
                (lazy-seq (cons small-prime
                            (rec (quot remaining small-prime) rp))))))]
   (rec n (primes))))


Factoring the problem this way, you can easily plug in an efficient way of generating primes.