SICP 연습문제 1.27 친절한 풀이

문제

원주 47에 나온 카마이클 수^{Carmichael number}가 참말 페르마 검사를 쓸모없게 만드는지 알아보자. 정수 $n$을 받아서 $a<n$인 모든 정수 $a$를 두고 $a^n$이 $a$와 $modulo$ $n$으로 맞아떨어지는지 알아보는 프로시저를 만든 다음, 이 프로시저로 카마이클 수를 검사해 보라.

문제로 부터 얻은 것

소수가 아님에도 불구하고 페르마 검사를 통과하는 수가 있다.

문제풀이

문제에서 요구하는 바에 맞게 기존의 코드를 아래와 같이 수정했습니다.

(define (fermat-test n k)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it k))

(define (prime?-iter n times)
  (cond ((= times 0) true)
        ((fermat-test n times) (prime?-iter n (- times 1)))
        (else false)))

(define (prime? n)
  (prime?-iter n (- n 1)))

그리곤 카마이클 수들을 시험해 보았습니다.
참고로 카마이클 수는 소수가 아님에도 불구하고 페르마 검사를 통과하는 수를 말합니다.

$561=3\times11\times17$
$1105=5\times13\times17$
$1729=7\times13\times19$
$2465=5\times17\times29$
$6601=7\times23\times41$

(prime? 561)
(prime? 1105)
(prime? 1729)
(prime? 2465)
(prime? 6601)

카마이클 수들은 모두 소수가 아님에도 페르마 검사를 통과하는 모습을 볼 수 있었습니다.

읽어주셔서 감사합니다.