Exercise 1.23. The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2 there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1). With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of the 12 primes found in exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is different from 2?
更高效的 smallest-divisor
(define (find-divisor n test-divisor)
(define (next num)
(cond ((even? num) (+ num 1))
(else (+ num 2))))
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))结果
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 *** 0
10039 *** 0
100001
100003 *** 1
100005
100007
100009
100011
100013
100015
100017
100019 *** 1
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 *** 1
1000035
1000037 *** 1
1000039 *** 1
10000001
10000003
10000005
10000007
10000009
10000011
10000013
10000015
10000017
10000019 *** 4
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 *** 4
10000105
10000107
10000109
10000111
10000113
10000115
10000117
10000119
10000121 *** 4
10000123
10000125
10000127
10000129
10000131
10000133
10000135
10000137
10000139 *** 4
10000141 *** 4
10000143
10000145
10000147
10000149
10000151
10000153
10000155
10000157
10000159
10000161
10000163
10000165
10000167
10000169 *** 4
10000171
10000173
10000175
10000177
10000179
10000181
10000183
10000185
10000187
10000189 *** 5
10000191
10000193
10000195
10000197
10000199
;... done
;Value: done
对比 练习 1.22 ，在大数上，修改过的 prime 时间是 4 ticks 左右，而之前是 7 左右，可以算是一倍的差值。