1.21
> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
>
1.22
在 DrScheme 中没有对应的 runtime 过程，我们用内建的 current-milliseconds
来代替，这个过程返回的是系统的 ms 数。
同时，在 Windows 下无法精确表示 16ms 以下的精度（可能时间片的大小是 16ms ），所以这里用比较大的数来测试。
代码如下
(define (even? x) (= (remainder x 2) 0))
(define (runtime) (current-milliseconds))
(define (start-prime-test n start-time)
(and (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (search-iter cur-num index start-time)
(newline)
(display cur-num)
(if (not (= index 0))
(if (start-prime-test cur-num start-time)
(search-iter (+ cur-num 2) (- index 1) start-time)
(search-iter (+ cur-num 2) index start-time))))
(define (search-for-primes start-number)
(if (even? start-number)
(search-iter (+ start-number 1) 3 (runtime))
(search-iter start-number 3 (runtime))))
这里用到了 prime? 谓词，代码不再复述。
|------+--------+--------+-------|
|10^9 | 10^10 | 10^11 | 10^12 | => start-number
|------+--------+--------+-------|
|31 | 250 | 609 | 1953 | (ms)
|47 | 406 | 1203 | 3844 |
|78 | 625 | 1859 | 5719 |
|------+--------+--------+-------|
从上表可以看出，除了前两列之间，后列的数字都是前列数字的 3 倍左右，近似于 √10 ≈ 3.16。实际上，随着 n 的不断增大，这个数会逐渐逼近 √10。
1.23
(define (next n)
(if (= n 2) 3 (+ n 2)))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
计算结果如下：
|--------+--------+-------|
| 10^10 | 10^11 | 10^12 | => start-number
|--------+--------+-------|
| 141 | 297 | 1078 | (ms)
| 219 | 609 | 2093 |
| 313 | 984 | 3140 |
|--------+--------+-------|
可以看出这个比值大约在 1.8(1/0.55) 左右，可能原因是其它的计算需要时间，但当 n 不断增大，其它计算是常数阶，这个比值会不断接近2。