問題1.27

僕の解答

こんな感じかな?

(define (square n)
	(* n n))

(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 (try-expmod n a)
	(= (expmod a n n) a))

(define (fermat-test-iter n a)
	(if (> a 0)
	    (and (try-expmod n a) (try-expmod n (- a 1)))
	  #t))

(define (fermat-test n)
	(fermat-test-iter n (- n 1)))

(define (println x)
	(display x)
	(newline))

(println (fermat-test 10))
(println (fermat-test 20))

(println (fermat-test 561))  ;3で割り切れる
(println (fermat-test 1105)) ;5で割り切れる
(println (fermat-test 1729)) ;7で割り切れる
(println (fermat-test 2465)) ;5で割り切れる
(println (fermat-test 2821)) ;7で割り切れる
(println (fermat-test 6601)) ;7で割り切れる


#f
#f
#t
#t
#t
#t
#t
#t
騙してますよ…と。