SICP 1.28 答案

其实，只要做一点点改写就可以达到目的了。

(define (square x)
      (* x x))

(define (nontrivial-check base m r)
  (cond ((and (not (= r 1)) 
              (not (= r (- m 1))) 
              (= (remainder (square r) m) 1)) 
         0)
        (else (square r))))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (nontrivial-check base m (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((miller-rabin-test n) (fast-prime? n (- times 1)))
        (else false)))

但是呢，既然是miller-rabin的检查，所以还是要改一改公式。

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))

下面这些检查都能通过

(fast-prime? 561 100)
(fast-prime? 1105 100)
(fast-prime? 1729 100)
(fast-prime? 2465 100)
(fast-prime? 2821 100)
(fast-prime? 6601 100)