1.21
> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
>
1.22
在 DrScheme 中沒有對應(yīng)的 runtime 過程，我們用內(nèi)建的 current-milliseconds
來代替，這個過程返回的是系統(tǒng)的 ms 數(shù)。
同時，在 Windows 下無法精確表示 16ms 以下的精度（可能時間片的大小是 16ms ），所以這里用比較大的數(shù)來測試。
代碼如下
(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? 謂詞，代碼不再復(fù)述。
|------+--------+--------+-------|
|10^9 | 10^10 | 10^11 | 10^12 | => start-number
|------+--------+--------+-------|
|31 | 250 | 609 | 1953 | (ms)
|47 | 406 | 1203 | 3844 |
|78 | 625 | 1859 | 5719 |
|------+--------+--------+-------|
從上表可以看出，除了前兩列之間，后列的數(shù)字都是前列數(shù)字的 3 倍左右，近似于 √10 ≈ 3.16。實(shí)際上，隨著 n 的不斷增大，這個數(shù)會逐漸逼近 √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)))))
計(jì)算結(jié)果如下：
|--------+--------+-------|
| 10^10 | 10^11 | 10^12 | => start-number
|--------+--------+-------|
| 141 | 297 | 1078 | (ms)
| 219 | 609 | 2093 |
| 313 | 984 | 3140 |
|--------+--------+-------|
可以看出這個比值大約在 1.8(1/0.55) 左右，可能原因是其它的計(jì)算需要時間，但當(dāng) n 不斷增大，其它計(jì)算是常數(shù)階，這個比值會不斷接近2。