So, Rich thinks I’m on a fool’s errand, but I’m going to keep going with this.

I’m sorry to say I can’t think of a less promising candidate for parallelization :( The 3 things you would want in something to parallelize are 
independent data/work, moderate-to-course-grained work units and/or 
complex coordination logic that would be simplified with threads. 
(Note – wanting it to run faster is not enough :) Here you have none of those – the data/work is interdependent (more 
later), the work is very fine grained (seq walk and a remainder test), 
and the logic was pretty elegant.

So, in order to have something to parallelize, I need to get one of those things. Since I am trying to make a list of primes, I’ll generate them two at a time. Each check is independent. There’s probably better ways to do it, but to keep my life simple, I’ll just generate pairs of primes lazily, but in parallel (each member of the pair in a separate thread).

Hmmm. I’m too tired to figure this out right now. So, for some content today, I can explain a mistake that Rich pointed out in my original prime sieve.

I defined primes as a function that returns a lazy seq, but a key benefit of lazy seqs is that they cache values — so by creating a new lazy seq for each call to primes, I lose caching. The right way is to define primes as a seq this way:

  (def primes (sieve (iterate inc 2)))

Then, when you do this:

  (time (reduce + (take 1000 primes)))
  (time (reduce + (take 1000 primes)))

You get this:

  “Elapsed time: 1080.253 msecs”
  “Elapsed time: 5.36 msecs”