SICPの問題を解こう14

問題1.27

素数以外でfermatテストを通ってしまう整数が本当に通るか確かめろという問題。

(define (fake-fermat-test n)
  (define (try-it a)
    (cond ((= a 1)
           (display "This num is prime or fake prime")
           (newline))
          ((= (expmod a n n) a)
           (try-it (- a 1)))
          (else
           (display "This num is not prime")
           (newline))))
  (try-it (- n 1)))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
(define (square x) (* x x))

(fake-fermat-test 561)
(fake-fermat-test 1105)
(fake-fermat-test 1729)
(fake-fermat-test 2465)
(fake-fermat-test 2821)
(fake-fermat-test 6601)

;;Just in case, test other case
(fake-fermat-test 1000) ;; not prime
(fake-fermat-test 1009) ;; prime

これで"This num is not prime"と表示されたのは1000だけで他の数値はfermatテストを通った。