;; ex 1.22 (define (square x) (* x x)) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (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)) (define (search-for-primes first last) (define (search-iter cur last) (if (<= cur last) (timed-prime-test cur)) (if (<= cur last) (search-iter (+ cur 2) last))) (search-iter (if (even? first) (+ first 1) first) (if (even? last) (- last 1) last))) (search-for-primes 1000 1019) ; 1e3 (search-for-primes 10000 10037) ; 1e4 (search-for-primes 100000 100043) ; 1e5 (search-for-primes 1000000 1000037) ; 1e6 ; As of 2008, computers have become too fast to appreciate the time ; required to test the primality of such small numbers. ; To get meaningful results, we should perform the test with numbers ; greater by, say, a factor 1e6. (newline) (search-for-primes 1000000000 1000000021) ; 1e9 (search-for-primes 10000000000 10000000061) ; 1e10 (search-for-primes 100000000000 100000000057) ; 1e11 (search-for-primes 1000000000000 1000000000063) ; 1e12

The output produced by the above code is:

1009 *** 0. 1013 *** 0. 1019 *** 0. 10007 *** 0. 10009 *** 0. 10037 *** 0. 100003 *** 0. 100019 *** 0. 100043 *** 0. 1000003 *** 0. 1000033 *** 0. 1000037 *** 1.0000000000000002e-2 1000000007 *** .13 1000000009 *** .11999999999999997 1000000021 *** .10999999999999999 10000000019 *** .39 10000000033 *** .3799999999999999 10000000061 *** .3700000000000001 100000000003 *** 1.22 100000000019 *** 1.2300000000000004 100000000057 *** 1.2199999999999998 1000000000039 *** 3.829999999999999 1000000000061 *** 4.039999999999999 1000000000063 *** 3.9700000000000006

From our timing data, we can observe that, when increasing the tested number of a factor 10, the required time increases roughly of a factor 3. By noting that 3 ≅ √10, we can confirm both the growth prediction and the notion that programs run in a time proportional to the steps required for the computation.

**Notes**

- This exercise requires a Scheme implementations which provides a
`runtime`primitive, such as MIT/GNU Scheme - The arguments to
`(search-for-primes`are an integer range. Therefore, to find the first three primes above a certain value, I needed to run the program with an arbitrary upper bound until three primes were found, and then put the third prime as the largest value. - In order to get a cleaner output, I modified
`timed-prime-test`to make it print only prime numbers, not each tested number. - By using the
`begin`construct, not introduced yet in the book, the inner procedure can be rewritten without repeating the`if`test:

```
(define (search-iter cur last)
(if (<= cur last)
(begin (timed-prime-test cur)
(search-iter (+ cur 2) last))))
```

<< Previous exercise (1.21) | sicp-solutions | Next exercise (1.23) >>