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