Project Euler Problem 3 in Clojure - part 1

This one is proving a bit tougher. First you need a list of prime numbers. I'm using the Euler's Sieve to produce primes.

First I wrote this function:

(defn sieve-numbers [position numbers]
  (if (>= position (count numbers))
  numbers
    (let [prime (nth numbers position)]
      (let [products (map #(* prime %) numbers)]
        (let [filtered (remove #(some #{%} products) numbers)]
          (recur (inc position) filtered))))))

which worked but was dog-slow:

;; (dotimes [_ 5] (time (sieve-euler 1000)))
;; "Elapsed time: 484.981564 msecs"
;; "Elapsed time: 459.624835 msecs"
;; "Elapsed time: 462.771112 msecs"
;; "Elapsed time: 460.312279 msecs"
;; "Elapsed time: 462.203786 msecs"
;; nil

To solve the problem we need to primes up to ceil(sqrt(N)) which is 775147 so that first method would take days.

To speed up the filtering I rewrote to use a SortedSet:

(defn sieve-numbers [primes candidates]
  (if (empty? candidates)
  primes
  (let [prime (first candidates)]
    (let [products (map #(* prime %) candidates)]
      (let [filtered (difference candidates products #{prime})]
        (recur (conj primes prime) filtered))))))

which is about 32 times faster:

;; (dotimes [_ 5] (time (sieve-euler 1000)))

;; "Elapsed time: 13.061787 msecs"
;; "Elapsed time: 12.994529 msecs"
;; "Elapsed time: 13.716897 msecs"
;; "Elapsed time: 13.237088 msecs"
;; "Elapsed time: 14.33136 msecs"

Still not good enough though. I need a faster sieve before I can even attempt to factor the large(ish) number and solve problem 3 inside a minute. I think my next step will be to pre-filter some of the non-primes with a Wheel Factorisation. This method wont remove all the non-primes, but it might be fun to implement.

I'm leaving the current sieve chugging away tonight to see how long it takes anyway, for comparison.