user> (let [sieve (fn sieve [[x & xs]]  
                    (lazy-cons x (sieve (filter #(pos? (rem % x)) xs))))]  
        (def primes (sieve (iterate inc 2))))  
#'user/primes  
user> (take 20 primes)  
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)  
user> (nth primes 1000)  
7927 

Diese Definition ist sicherlich nichts für die praktische Anwendung, aber dafür ist sie unterhaltsam.