Goldbach Pairs

Description of the Problem

The famous Goldbach Conjecture states that every even integer is a sum of two odd primes. Today, I will write a small program to split an even number into a sum of two odd primes. The conjecture states that this function I am about to define always returns a non-trivial pair of primes splitting the given even integer.

Code

First a simple function to test whether a given number is prime:

(defun primep (n)
   (if (oddp n)
       (let ((m (floor (sqrt n))))
          (do ((i 3 (+ i 2)))
              ((or (> i m) (zerop (mod n i)))
               (and (> i m) n))))))
PRIMEP

The function will return nil if the number is composite, otherwise returns the number n which is prime.

Next, I have a function which will return the first prime number coming after a given integer.

(defun next-prime (n)
   (cond ((< n 2) 2)
         ((= n 2) 3)
         (t (let ((m (if (evenp n) (1+ n) (+ n 2))))
               (or (primep m)
                   (next-prime m))))))
NEXT-PRIME

Now, a function which returns the first Goldbach pair

(defun goldbach-pair (n)
   (if (evenp n)
      (do ((i 3 (next-prime i)))
          ((primep (- n i)) (list i (- n i))))))
GOLDBACH-PAIR

Let us test:

(goldbach-pair (expt 2 40))
(167 1099511627609)

Finally, a function which returns all Goldbach pairs:

(defun all-goldbach-pairs (n)
   (if (evenp n)
       (let ((m (/ n 2))
             (res nil))
          (do ((i 3 (next-prime i)))
              ((> i m) (reverse res))
              (if (primep (- n i))
                  (push (list i (- n i)) res))))))
ALL-GOLDBACH-PAIRS

And its test

(all-goldbach-pairs (expt 2 10))
((3 1021) (5 1019) (11 1013) (41 983) (47 977) (53 971) (71 953) (83 941)
 (113 911) (137 887) (167 857) (197 827) (227 797) (251 773) (263 761)
 (281 743) (347 677) (383 641) (431 593) (461 563) (467 557) (503 521))