(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a)) ; (random i) returns integer in range [0, i - 1] (try-it (+ 1 (random (- n 1))))) (define (fast-prime? n times) (cond ((= times 0) #t) ((fermat-test n) (fast-prime? n (- times 1))) (else #f))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time) (newline)) (define (start-prime-test n start-time) (if (fast-prime? n 256) (report-prime (- (runtime) start-time)))) (define (timed-prime-test 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 (= (remainder n 2) 0) (+ n 1) n)) (define (iter n) (cond ((> n b)) (else (timed-prime-test n) (iter (+ n 2))))) (iter (first-odd a))) ; 10^15 ~0.03 seconds ; 10^18 ~0.04 seconds ; 10^21 ~0.05 seconds ; 10^24 ~0.06 seconds ; 10^25 ~0.07 seconds ; 1000x the input size increases the runtime by a fixed amount. This is ; consistent with a logarithmic runtime algorithm.