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