問題1.23

(defun next-divisor (n)
  (if (= n 2)
      3
      (+ n 2)))

(defun find-divisor (n test-divisor)
  (cond ((> (expt test-divisor 2) n) n)
        ((dividesp test-divisor n) test-divisor)
        (t (find-divisor n (next-divisor test-divisor)))))

問題1.22のバージョンでの計測結果は、

> (mapc #'(lambda (n)
            (timed-prime-test n))
        '(1009 1013 1019
          10007 10009 10037
          100003 100019 100043
          1000003 1000033 1000037))

1009 *** 18605
1013 *** 10713
1019 *** 10994
10007 *** 25079
10009 *** 25055
10037 *** 25061
100003 *** 73716
100019 *** 74464
100043 *** 74554
1000003 *** 225458
1000033 *** 229998
1000037 *** 225387
(1009 1013 1019 10007 10009 10037 100003 100019 100043 1000003 1000033 1000037)

nextを使ったバージョンの計測結果は、

> (mapc #'(lambda (n)
            (timed-prime-test n))
        '(1009 1013 1019
          10007 10009 10037
          100003 100019 100043
          1000003 1000033 1000037))

1009 *** 12869
1013 *** 6695
1019 *** 6336
10007 *** 13707
10009 *** 14019
10037 *** 13785
100003 *** 39834
100019 *** 38745
100043 *** 38475
1000003 *** 112975
1000033 *** 112921
1000037 *** 112813
(1009 1013 1019 10007 10009 10037 100003 100019 100043 1000003 1000033 1000037)

となり、速度の比は平均で約1.8になった。

ステップが半分になった代わりに、ステップごとにnextが呼ばれ、その中でnと2の比較が行われるようになったため、単純に速度の比は2にならない。