(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.