My brain still hurts from thinking about parallelizing prime number generation. I think the key is still to find primes two at a time in parallel, meaning that it’s only useful if you want a list, which is necessary to find the nth prime anyway.

So, I am starting with a rewrite of prime number generation — this one is simpler for me to understand and for some reason runs three times faster.

  (defn divisible? [x y]
      (= (rem x y) 0)
  )

  (defn is-prime? [p known-primes]
      (every? (fn [kp] (not (divisible? p kp))) known-primes)
  )

  (defn primes-in-list [potential-primes known-primes]
      (let [p (first potential-primes)]
          (if (is-prime? p known-primes)
              (lazy-cons
                  p
                  (primes-in-list (rest potential-primes) (conj known-primes p)))
              (primes-in-list (rest potential-primes) known-primes)
          )
      )
  )

  (def primes (primes-in-list (iterate inc 2) []))
  (time (reduce + (take 1000 primes)))
  (time (reduce + (take 1000 primes)))

It’s also lazy. Not sure why it’s so much faster. Now that I can provide a list of potentials, I’ll be able to run two lists in parallel, and then I have to reduce them in the main thread. When I get the lists back, I need to make sure that they aren’t divisible by each other (since they won’t be in each others list of known primes).