(define (divides? a b) (= (remainder b a) 0))
(define (smallest-divisor n)
(define (next test-divisor)
(if (= test-divisor 2) 3 (+ test-divisor 2)))
(define (find-divisor test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor (next test-divisor)))))
(find-divisor 2))
(define (prime? n) (= (smallest-divisor n) n))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
; Search for primes in the range [a, b]
(define (search-for-primes a b)
; Find first odd integer >= n
(define (first-odd n)
(if (divides? 2 n) (+ n 1) n))
(define (iter n)
(cond ((> n b))
(else (timed-prime-test n)
(iter (+ n 2)))))
(iter (first-odd a)))
; The runtime using next is about the same as (+ test-divisor 1).
; Next is slower than (+ test-divisor 1) because it is a user defined function
; which performs comparisons in addition to an addition while + is a build in
; operator.
; The overhead of next must be enough to offset the work avoided by skipping
; even numbers. The constant overhead of starting up the interpreter must not
; be a significant factor because the runtimes are about the same even for
; larger inputs where the startup time is a small fraction of total runtime.