#
Smallest primes
^{
}

Most Lisp implementations include a primitive called
`runtime`

that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following
`timed-prime-test`

procedure, when called with an integer
`n`

, prints
`n`

and checks to see if
`n`

is prime. If it's prime, the procedure prints three asterisks followed by the amount of time used in performing the test.

```
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
```

Using this procedure, write a procedure
`search-for-primes`

that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of Θ(√n), you should expect that testing for primes around 10,000 should take about √10 times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the √n prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?

```
;#lang racket/base
;(require rackunit)
;(require sicp)
(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)
(= (smallest-divisor n) n))
(define (timed-prime-test n out)
(newline)
(display n out)
(start-prime-test n (runtime) out))
(define (start-prime-test n start-time out)
(if (prime? n)
(report-prime (- (runtime) start-time) out)))
(define (report-prime elapsed-time out)
(display " *** " out)
(displayln (floor elapsed-time) out))
(define op1 (open-output-string))
(search-for-primes 1 6 op1)
(define display-result (get-output-string op1))
(check-equal? display-result "1 *** 0\n3 *** 0\n5 *** 0\n")
(close-output-port op1)
```