euler010.clj

; Problem 10
; 
; The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
; 
; Find the sum of all the primes below two million.

(defn prime? [x]
  (cond (< x 2) false
	(= x 2) true
	(even? x) false
	:else (let [boundary (inc (bigint (Math/sqrt x)))
		    candidates (range 3 boundary 2)]
		(empty? (drop-while #(pos? (mod x %)) candidates)))))

; Slow version, test all odd numbers
(defn sum-of-primes-upto [limit] 
  (loop [x 3 sum 2]
    (if (< x limit)
      (if (prime? x)
	(recur (+ x 2) (+ x sum))
	(recur (+ x 2) sum))
      sum)))

; Fast version, use Sieve of Eratosthenes
(defn sum-of-primes-upto* [limit] 
  (let [sieve (doto (java.util.BitSet.) (.set 1))] ; mark 1 as non-prime, rest as candidates,
    (loop [n 3 sum 2]                              ; skipping even numbers
      (cond
       (>= n limit)
       sum 
       (false? (.get sieve n))                     ; n is a prime
       (do
	 (doseq [x (range (+ n n) limit n)]
	   (.set sieve x))                         ; mark all multiples as non-prime
	 (recur (+ n 2) (+ sum n)))
       (true? (.get sieve n))                      ; previously marked non-prime
       (recur (+ n 2) sum)))))



(def answer (future (sum-of-primes-upto 2000000)))