1.22

练习 1.22： 大部分 Lisp 实现都包含一个 runtime 基本过程，调用它将返回一个整数，表示系统已经允许的时间（例如，以微秒计）。在对整数 n 调用下面的 timed-prime-test 过程时，将打印出 n 并检查 n 是否是素数。如果 n 是素数，过程将打印出三个星号，随后是执行这一检查所用的时间量。

(define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time))

请利用这一过程写一个 search-for-primes 过程，它检查给定范围内连续的各个奇数的素性。请用你的过程找出大于 1 000、大于 10 000、大于 100 000 和大于 1 000 000 的三个最小素数。请注意其中检查每个素数所需要的时间。因为这一检查算法具有 Θ(n)\Theta(\sqrt n) 的增长阶，你可以期望在 10 000 附近的素数检查的耗时大约是在 1 000 附近的素数检查的 10\sqrt{10} 倍。你得到的数据确实如此吗？对于 100 000 和 1 000 000 得到的数据，对这一 n\sqrt n 预测的支持情况如何？有人说程序在你的机器上运行的时间正比于计算所需的步数，你得到的结果符合这种说法吗？

先看下 timed-prime-test 执行的效果：