November 29, 2008

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

This solution tests if a number is prime by testing if the number's smallest divisor is equal to itself. It then loops through all the odd numbers by two and sums the primes.

;;; Functions for testing if a number is prime
(defun square (x) (* x x))

(defun dividesp (a b)
(zerop (mod b a)))

(defun find-divisor (n test-divisor)
(cond ((> (square test-divisor) n) n)
((dividesp test-divisor n) test-divisor)
(t (find-divisor n (+ test-divisor 1)))))

(defun smallest-divisor (n)
(find-divisor n 2))

(defun primep (n)
(= n (smallest-divisor n)))

;;; End of prime functions

(defun sum-of-primes-below (num)
"Returns the sum of all the prime numbers below num"
(+ 2 (loop for i from 3 to num by 2 when (primep i) sum i)))

(defun euler-10 ()
(sum-of-primes-below 2000000))