(define (divides? a b) (= (remainder b a) 0))

(define (smallest-divisor n)
  (define (find-divisor test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor (+ test-divisor 1)))))
  (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)))

; Primes larger than 1000
; 1009 1013 1019

; Primes larger than 10000
; 10007 10009 10037

; Primes larger than 100000
; 100003 100019 100043

; Primes larger than 1000000
; 1000003 1000033 1000037

; 10^8 ~0.02 seconds
; 10^9 ~0.05 seconds
; 10^10 ~0.14 seconds
; 10^11 ~0.4 seconds
; 10^12 ~1.2 seconds
; There is about a 3x increase in runtime for each 10x increase in input size.
; sqrt(10) ~ 3.16 so this behavior is consistent with an O(sqrt(n)) algorithm.