Problem 010: Summation of primes

From Project Euler:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

My initial approach to this was to do something using the Sieve of Eratosthenes, and my solution was something like this:

(defn prime-sieve-sum [n]
  (loop [nums (vec (concat [2] (range 3 n 2)))
         total 0]
    (if (empty? nums)
      total
      (let [current (first nums)]
        (recur (vec (remove #(== 0 (mod % current)) (rest nums)))
               (+ current total))))))

This keeps a vector of all the possible primes, and filters out any multiples as it goes along. The downside is that this was very slow: it took about 10 minutes to run on my machine with $n$ at 2 million.

My guess is that since it is constantly creating new vectors, there is a lot of memory copying going on. A better approach might be to keep a large vector of bools and set them to false as each multiple is encountered. This doesn't jive well with Clojure's immutable vectors, but you can fall back to Java's ArrayList if you want to do this approach.

Instead I just decided to brute force it. Using the is-prime? function from Problem 003, I just scanned across:

(defn prime-sum [n]
  (loop [current 3
         total 2]
    (if (>= current n)
      total
      (recur (+ 2 current)
             (+ total (if (is-prime? current)
                        current
                        0))))))

This gets the job done much more quickly (about 5s overhead for lein/JVM):

$ time lein run
Running...
142913828922

real 0m21.508s
user 0m22.936s
sys 0m0.530s