Exercise 1.22. Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in performing the test.
(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))
Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of (n), you should expect that testing for primes around 10,000 should take about 10 times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the n prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?
mit-scheme 的 runtime 过程返回的时间单位是秒，是没有办法得到我们想看到的结果的。我们可以使用 real-time-clock 来返回毫秒。
(define (current-time)
(real-time-clock))
(define (search-for-primes s e)
(cond ((> s e) 'done)
((even? s) (search-for-primes (+ 1 s) e))
(else
(begin (timed-prime-test s)
(search-for-primes (+ 1 s) e)))))
(define search
(lambda ()
(search-for-primes 1000 1020)
; smallest primes are 1009 1013 1019
(search-for-primes 10000 10040)
; smallest primes are 10007 10009 10037
(search-for-primes 100000 100050)
; smallest primes are 100003 100019 100043
(search-for-primes 1000000 1000040)
; smallest primes are 1000003 1000033 1000037
(search-for-primes 10000000 10000200)))下面是运行之后的结果
1001
1003
1005
1007
1009 *** 0
1011
1013 *** 0
1015
1017
1019 *** 0
10001
10003
10005
10007 *** 0
10009 *** 0
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037 *** 1
10039 *** 0
100001
100003 *** 1
100005
100007
100009
100011
100013
100015
100017
100019 *** 0
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043 *** 0
100045
100047
100049 *** 0
1000001
1000003 *** 2
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033 *** 4
1000035
1000037 *** 4
1000039 *** 2
10000001
10000003
10000005
10000007
10000009
10000011
10000013
10000015
10000017
10000019 *** 8
10000021
10000023
10000025
10000027
10000029
10000031
10000033
10000035
10000037
10000039
10000041
10000043
10000045
10000047
10000049
10000051
10000053
10000055
10000057
10000059
10000061
10000063
10000065
10000067
10000069
10000071
10000073
10000075
10000077
10000079 *** 7
10000081
10000083
10000085
10000087
10000089
10000091
10000093
10000095
10000097
10000099
10000101
10000103 *** 7
10000105
10000107
10000109
10000111
10000113
10000115
10000117
10000119
10000121 *** 6
10000123
10000125
10000127
10000129
10000131
10000133
10000135
10000137
10000139 *** 10
10000141 *** 6
10000143
10000145
10000147
10000149
10000151
10000153
10000155
10000157
10000159
10000161
10000163
10000165
10000167
10000169 *** 5
10000171
10000173
10000175
10000177
10000179
10000181
10000183
10000185
10000187
10000189 *** 6
10000191
10000193
10000195
10000197
10000199
数字越大，运算得越精确，因为系统本身的时钟精度对于运算较小的数字就是不准确的。一直到把数字从 1000000 提高到 10000000 的时候，可以看到时钟的区间从 [2, 4] 提高到了 [5, 10]，基本上可以看做是