# 1.25

## 练习 1.25：Alyssa P. Hacker 提出，在写 expmod 时我们做了过多的额外工作。她说，毕竟我们已经知道怎样计算乘幂，因此只需要简单地写：

(define (expmod base exp m) (remainder (fast-expt base exp) m))

### 先测试一下使用这个建议的效果

(define (fast-expt b n) (cond ((= n 0) 1) ((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1)))))) (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false) ) ) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ 1 (random (- n 1)))) ) (define (expmod base exp m) (remainder (fast-expt base exp) m) ) (define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (fast-prime? n 5) (report-prime (- (runtime) start-time)) (display " 不是素数！"))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) (define (square x) (* x x)) (timed-prime-test 7) (timed-prime-test 14)

### 分别找出大于 1 000、10 000、100 000、1 000 000 的三个最小素数。

(define (fast-expt b n) (cond ((= n 0) 1) ((even? n) (square (fast-expt b (/ n 2)))) (else (* b (fast-expt b (- n 1)))))) (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false) ) ) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ 1 (random (- n 1)))) ) (define (expmod base exp m) (remainder (fast-expt base exp) m) ) (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false) ) ) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ 1 (random (- 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 (timed-prime-test n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (fast-prime? n 5) (report-prime n (- (runtime) start-time)) #f)) (define (square x) (* x x)) (define (report-prime n elapsed-time) (newline) (display n) (display " *** ") (display elapsed-time) (display ", 它的 \\log{n} 倍时间是 ") (display (* elapsed-time (log elapsed-time))) ) (define (timed-prime-test-between n1 n2 found) (if (timed-prime-test n1) (if (or (> found 1) (> n1 n2)) (display " 测试结束！ ") (timed-prime-test-between (+ n1 1) n2 (+ found 1)) ) (if (> n1 n2) (display " 测试结束！ ") (timed-prime-test-between (+ n1 1) n2 found) ) ) ) (newline) (display "大于 1000 的三个最小素数：") (timed-prime-test-between 1001 9999 0) (newline) (newline) (display "大于 10 000 的三个最小素数：") (timed-prime-test-between 10001 99999 0) (newline) (newline) (display "大于 100 000 的三个最小素数：") (timed-prime-test-between 100001 999999 0) (newline) (newline) (display "大于 1 000 000 的三个最小素数：") (timed-prime-test-between 1000001 9999999 0) (newline)