SICP по-русски

Это упражнение является логическим продолжением предыдущего упражнения 22, поэтому ознакомьтесь с его решением прежде, чем продолжать.

Итак, измененный код процедуры (find-divisor) будет выглядеть так:

(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)))))

Результаты запусков тестов из предыдущего упражнения таковы:

> (search-for-primes 100000000000 3)
100000000003 *** 516
100000000019 *** 235
100000000057 *** 516

> (search-for-primes 1000000000000 3)
1000000000039 *** 1031
1000000000061 *** 1016
1000000000063 *** 1031

> (search-for-primes 10000000000000 3)
10000000000037 *** 3515
10000000000051 *** 3453
10000000000099 *** 3469

> (search-for-primes 100000000000000 3)
100000000000031 *** 11203
100000000000067 *** 11032
100000000000097 *** 11000

А вот сравнительная таблица:

Можно говорить, что для достаточно больших чисел ускорение действительно практически в два раза. Для маленьких чисел это не так, что можно объяснить, в первую очередь, увеличившимися накладными расходами в процедуре (find-divisor), которые “съедают” выигрыш от усечения множества перебираемых кандидатов в простые числа.