P31: 引数として渡された整数が素数かどうかを検査

SICPの1.2.6から。

;; P31
(defun square (x) (* x x))
(defun expmod (base exp m)
  (cond ((= exp 0) 1)
	((evenp exp)
	 (rem (square (expmod base (/ exp 2) m)) m))
	(t
	 (rem (* base (expmod base (- exp 1) m)) m))))

(defun fermat-test (n)
  (labels ((try-it (a)
		   (= (expmod a n n) a)))
    (try-it (+ 1 (random (- n 1))))))

(defun prime-p (n &optional (times 10))
  (check-type n integer)
  (check-type times integer)
  (labels ((iter (times)
		 (cond
		  ((<= times 0) t)
		  ((fermat-test n) (iter (1- times)))
		  (t nil))))
    (cond
     ((<= n 1) nil)
     (t (iter times)))))
      
(mapcar (lambda (n)
	  (prime-p n)) '(0 1 2 3 4 5 6 7 8 9 10 11))
;; => (NIL NIL T T NIL T NIL T NIL NIL NIL T)