Functional Sieve of Eratosthenes in Clojure
Is there a way to avoid the cond dispatch in naïve-prime??


You could do naive-prime? this way:

(defn naive-prime? [n]
  (and
       (&gt;= n 2)
       (-&gt;&gt; n
            (inc)
            (Math/sqrt)
            (range 2)
            (not-any? #(zero? (rem n %))))))


This gets rid of the special cases 1 and 2. The trick is to increment before applying Math/sqrt, so that the edge case 2 works correctly. 

I've also elided the not into the some to produce not-any?.


  I'd mainly like recommendations for speeding this up.


Try

(defn sieve-primes [n]
  (loop [p 2 ; First prime
         marked #{} ; Found composites
         primes []]
    (let [mults (range (* p p) (inc n) p)
          next-p (-&gt;&gt; p
                      (inc)
                      (iterate inc)
                      (remove marked)
                      (first))

          new-primes (conj primes p)]

      (if (&gt;= (* next-p next-p) n)
        (into new-primes (remove marked (range next-p (inc n)))


There are a couple of changes here. 


Generate  mults as a range, starting at (* p p) - the first
number that needs to be tested with prime factor p.
Stop testing when the prime you would use, next-p, squared is
bigger than the limit n.


I don't like the idea of building a massive set of composites. Better turn the algorithm inside out and test each number as it occurs against only the necessary prime factors. But that's a quite different algorithm.