問題1.28

僕の解答

とりあえず、途中まで考えたとこでギブ…

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

(define (expmod base exp m)
	(cond ((= exp 0) 1)
	      ((even? exp)
	       (let* ((x (expmod base (/ exp 2) m))
		      (y (square x)))
		 (if (and (not (= y 1))
			  (not (= y (- m 1)))
			  (= (remainder (square y) m) 1))
		     0
		   (remainder x m))))
	      (else
	       (remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test n)
	(define (try-it a)
		(let ((x (expmod a n n)))
		  (or (= x a) (= x -1))))
	(try-it (+ 1 (random (- n 1)))))

;(define (fast-prime? n)
;	(fermat-test n))

(define (fast-prime? n times)
	(cond ((= times 0) #t)
	      ((fermat-test n) (fast-prime? n (- times 1)))
	      (else #f)))

(let ((n (fast-prime? 5 10)))
  (display n)
  (newline))

所感

うーん、問題文からワケワカ。
答え見て、いろいろ試してみたけど…orz