This exercise is based on sicp-ex-1.22. Please read the notes therein.

  
 ;; ex 1.23 
  
 (define (square x) (* x x)) 
  
 (define (smallest-divisor n) 
   (find-divisor n 2)) 
  
 (define (find-divisor n test-divisor) 
   (define (next n) 
     (if (= n 2) 3 (+ n 2))) 
   (cond ((> (square test-divisor) n) n) 
         ((divides? test-divisor n) test-divisor) 
         (else (find-divisor n (next test-divisor))))) 
  
 (define (divides? a b) 
   (= (remainder b a) 0)) 
  
 (define (prime? n) 
   (= n (smallest-divisor n))) 
  
 (define (timed-prime-test n) 
   (start-prime-test n (runtime))) 
  
 (define (start-prime-test n start-time) 
   (if (prime? n) 
       (report-prime n (- (runtime) start-time)))) 
  
 (define (report-prime n elapsed-time) 
   (newline) 
   (display n) 
   (display " *** ") 
   (display elapsed-time)) 
  
 (timed-prime-test 1009) 
 (timed-prime-test 1013) 
 (timed-prime-test 1019) 
 (timed-prime-test 10007) 
 (timed-prime-test 10009) 
 (timed-prime-test 10037) 
 (timed-prime-test 100003) 
 (timed-prime-test 100019) 
 (timed-prime-test 100043) 
 (timed-prime-test 1000003) 
 (timed-prime-test 1000033) 
 (timed-prime-test 1000037) 
  
 ; See comments in exercise 1.22 
 (newline) 
 (timed-prime-test 1000000007) 
 (timed-prime-test 1000000009) 
 (timed-prime-test 1000000021) 
 (timed-prime-test 10000000019) 
 (timed-prime-test 10000000033) 
 (timed-prime-test 10000000061) 
 (timed-prime-test 100000000003) 
 (timed-prime-test 100000000019) 
 (timed-prime-test 100000000057) 
 (timed-prime-test 1000000000039) 
 (timed-prime-test 1000000000061) 
 (timed-prime-test 1000000000063)

The output produced by the above code is:

1009 *** 0.
1013 *** 0.
1019 *** .01
10007 *** 0.
10009 *** 0.
10037 *** 0.
100003 *** 0.
100019 *** 0.
100043 *** 0.
1000003 *** 0.
1000033 *** .01
1000037 *** 0.

1000000007 *** .08
1000000009 *** .09
1000000021 *** .08000000000000002
10000000019 *** .25
10000000033 *** .26
10000000061 *** .27
100000000003 *** .8299999999999998
100000000019 *** .8200000000000003
100000000057 *** .7999999999999998
1000000000039 *** 2.6500000000000004
1000000000061 *** 2.59
1000000000063 *** 2.59

The observed ratio of the speed of the two algorithms is not 2, but roughly 1.5 (or 3:2).

This is mainly due to the NEXT procedure's IF test. The input did halve indeed, but we need to do an extra IF test.

sicp-ex-1.23