Project Euler in Clojure – Problem 10

This is my solution to Problem 10 of Project Euler. As always, my progress you can tracked on GitHub at https://github.com/stevenproctor/project-euler-clojure.

Problem 10 of Project Euler is described as:

Find the sum of all the primes below two million.

And my solution for this, including previously defined functions created as part of solving the previous problems, is the following:

(defn square [n]
  (* n n))

(defn sum [s]
  (reduce + s))

(defn primes-under2 [n]
  (let [sieve (transient (set (cons 2 (range 3 n 2))))]
    (loop[s sieve
           f 3]
      (cond (> (square f) n) (persistent! s)
            :else (recur (reduce disj! s (range (square f) n f)) (inc f))))))

(defn problem10
  ([] (problem10 2000000))
  ([n] (bigint (sum (primes-under2 n)))))

The functions sum and square came from the suggestion of Arcane Sentiment in a comment on a previous problem, as well as a post of his Square in R7RS.

The function primes-under2, is my second attempt at creating the primes under a given number using the Sieve of Eratosthenes. The short description is that the function uses sets of multiples of each integral number up to the square root of the number specifies and removes those items from the set. A more detailed write up can be found in my post Sieve of Eratosthenes in Clojure using Sets.

With those functions defined, I simply get the sum of the call to primes-under2 and make it a bigint to try to ensure the sum will be handled nicely for large numbers, but looking at it now, it is probably not even needed.

**Update**
I have posted my solution to Problem 11.

–Proctor

Leave a Reply

Your email address will not be published. Required fields are marked *