Clojure code for finding prime numbers

(non-Clojure-specific) Gain performance, sure. Use packed array of odds, where index i represents value 2i+1. Then you don't have to deal with evens, which are all non-prime a priori (except the 2 of course). Then you can increment by 2*p for a prime p to find its odd multiples twice faster.

For a non-marked index i, the prime p is p = 2*i+1, its square is p*p = (2i+1)(2i+1) = 4i^2 + 4i + 1 and its index is (p*p-1)/2 = 2i^2 + 2i = 2i(i+1) = (p-1)(i+1). For the value increment of 2*p, the index increment on 2x-packed array is di = p = 2i+1.

I've played around with your code to try to understand it, frankly. After a long sequence of changes, I ended up with the following:

(defn primes [n]
  (let [mark (fn [i di v]
               (reduce
                 (fn [w i] (assoc w i di))
                 v
                 (range i (count v) di)))
        [answer &_] (reduce
                      (fn [[ps v :as both] i]
                        (if (= (v i) 1)
                          [(conj ps i) (mark (* i i) i v)]
                          both))
                      (let [init-v (->> (repeat 1) (take n) (vec))]
                        [[] init-v])
                      (range 2 n))]
    answer))

• I've got rid of the decs in all the accesses to the vector v.
• I've captured the recurs, in the mark and step functions, in reduces.
• Since the step function is no longer recursive, I've unwrapped it into its one call.

The new mark function is a little faster. But the step equivalent is going to be slower, since it generates a new pair-vector for every prime.

The main problem here is space - your vector v is the size of your candidate range of numbers. I've come across a cute algorithm that gets round this, though at some cost in speed, spent on laziness.