1 (define (expmod base exp m)
2   (cond ((= exp 0) 1)
3 	((even? exp)
4 	 (remainder (square (expmod base (/ exp 2) m)) m))
5 	(else (remainder (* base (expmod base (- exp 1) m)) m))))
6 
7 (define (fermat-test n)
8   (define (try-it a)
9     (= (expmod a n n) a))
10   (try-it (+ 1 (random (- n 1)))))
11 
12 (define (fast-prime? n times)
13   (cond ((= times 0) true)
14 	((fermat-test n) (fast-prime? n (- times 1)))
15 	(else false)))
16 
17 (define (smallest-divisor n)
18   (find-divisor n 2))
19 (define (find-divisor n test-divisor)
20   (cond ((> (square test-divisor) n) n)
21 	((divides? test-divisor n) test-divisor)
22 	(else (find-divisor n (+ test-divisor 1)))))
23 (define (divides? a b)
24   (= (remainder b a) 0))
25 (define (prime? n)
26   (= n (smallest-divisor n)))
27 
28 (define (test-case actual expected)
29   (load-option 'format)
30   (newline)
31   (format #t "Actual: ~A Expected: ~A" actual expected))
32 
33 (define (timed-prime-test n)
34   (newline)
35   (display n)
36   (start-prime-test n (runtime)))
37 (define (start-prime-test n start-time)
38   (if (prime? n)
39       (report-prime (- (runtime) start-time))))
40 (define (report-prime elapsed-time)
41   (display " *** ")
42   (display elapsed-time))
43 
44 (define (search-for-primes lower upper)
45   (cond ((even? lower) (search-for-primes (+ lower 1) upper))
46 	((< lower upper) (begin (timed-prime-test lower)
47 				(search-for-primes (+ lower 2) upper)))
48 	(else (newline)
49 	      (display " *** Finished *** "))))
50 
51 (search-for-primes 100000001 100000099)
52 (search-for-primes 1000000001 1000000099)
53 (search-for-primes 10000000001 10000000099)
54 (search-for-primes 100000000001 100000000099)
55 (search-for-primes 1000000000001 1000000000099)
56 (search-for-primes 10000000000001 10000000000099)
57 (search-for-primes 100000000000001 100000000000099)
58 
59 ;; see spreadsheet for results and charts
60 
61 ;; Yes, our timing data perfectly fits the order of growth prediction that R(n) is of the order sqrt(n). So, it seems that our programs do run in time proportional to number of steps required.
62