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 (test-case actual expected)
18 ;;   (load-option 'format)
19 ;;   (newline)
20 ;;   (format #t "Actual: ~A Expected: ~A" actual expected))
21 
22 
23 ;; Exercise 1.24.  Modify the timed-prime-test procedure of exercise 1.22 to use fast-prime? (the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has (log n) growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find? 
24 
25 ;; (define (smallest-divisor n)
26 ;;   (find-divisor n 2))
27 ;; (define (find-divisor n test-divisor)
28 ;;   (define (next-divisor n)
29 ;;     (if (= n 2)
30 ;; 	3
31 ;; 	(+ n 2)))
32 ;;   (cond ((> (square test-divisor) n) n)
33 ;; 	((divides? test-divisor n) test-divisor)
34 ;; 	(else (find-divisor n (next-divisor test-divisor)))))
35 ;; (define (divides? a b)
36 ;;   (= (remainder b a) 0))
37 ;; (define (prime? n)
38 ;;   (= n (smallest-divisor n)))
39 
40 (define (prime? n)
41   (let ((times-to-test 10))
42     (fast-prime? n times-to-test)))
43 
44 (define (timed-prime-test n)
45   (newline)
46   (display n)
47   (start-prime-test n (runtime)))
48 (define (start-prime-test n start-time)
49   (if (prime? n)
50       (report-prime (- (runtime) start-time))))
51 (define (report-prime elapsed-time)
52   (display " *** ")
53   (display elapsed-time))
54 
55 (define (search-for-primes lower upper)
56   (cond ((even? lower) (search-for-primes (+ lower 1) upper))
57 	((< lower upper) (begin (timed-prime-test lower)
58 				(search-for-primes (+ lower 2) upper)))
59 	(else (newline)
60 	      (display " *** Finished *** "))))
61 
62 
63 (search-for-primes 100000000000001 100000000000099)
64 (search-for-primes 1000000000000001 1000000000000099)
65 (search-for-primes 10000000000000001 10000000000000099)
66 (search-for-primes 100000000000000001 100000000000000099)
67 (search-for-primes 1000000000000000001 1000000000000000099)
68 (search-for-primes 10000000000000000001 10000000000000000099)
69 
70 ;;can't even test due to small numbers being too fast
71