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)