Sunday, April 10, 2016

Project Euler Problem 46 Common Lisp

Project Euler Problem 46

Note that all square integers from 1 to some number can be found by summing all the odd numbers, e.g. 2 *2 = 4 = 1 + 3, 3 * 3 = 9 = 1 + 3 + 5, 4 * 4 = 16 = 1 + 3 + 5 + 7.  That's what is happening in function conjecture-false?

(defun prime? (num)
  (cond ((= 2 num) num)
    ((= 3 num) num)
    ((< num 1) nil)
    ((evenp num) nil)
    ((zerop (mod num 3)) nil)
    (t (loop for i from 5 to (isqrt num) by 6
        if (or (zerop (mod num i))
               (zerop (mod num (+ i 2)))) return nil
        finally (return num)))))

(defun conjecture-false? (num)
  (loop for i from 1 to num by 2
       sum i into j
       if (prime? (- num (* j 2))) return nil
       finally (return t)))

(defun problem46 ()
  (loop for i upfrom 1 by 2
       unless (prime? i)
       when (conjecture-false? i) return i))

No comments:

Post a Comment