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?
练习 1.23：本节开头给出的 smallest-divisor 过程做了许多不必要的检验：检查数是否能被 2 整除之后，再去检查能否被更大的偶数整除就毫无意义了。这表明 test-divisor 所取的值应当不是 2, 3, 4, 5, 6, …，而应当是 2, 3, 5, 7, 9, …。为此，定义一个过程 next：若其输入等于 2 则返回 3，否则返回其输入加 2。将 smallest-divisor 中的 (+ test-divisor 1) 改为 (next test-divisor)。在将这一修改后的 smallest-divisor 版本纳入 timed-prime-test 之后，对练习 1.22 中找到的 12 个素数运行检验。由于这一修改使检验步骤数减半，你应当预期速度约提高一倍。这一预期是否得到验证？若否，两种算法速度之比的实测值是多少？如何解释它与 2 不同这一事实？