# sicp-ex-1.23

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.