1 665c255d 2023-08-04 jrmu (define (expmod base exp m)
 2 665c255d 2023-08-04 jrmu   (cond ((= exp 0) 1)
 3 665c255d 2023-08-04 jrmu 	((even? exp)
 4 665c255d 2023-08-04 jrmu 	 (remainder (square (expmod base (/ exp 2) m)) m))
 5 665c255d 2023-08-04 jrmu 	(else (remainder (* base (expmod base (- exp 1) m)) m))))
 6 665c255d 2023-08-04 jrmu 
 7 665c255d 2023-08-04 jrmu (define (fermat-test n)
 8 665c255d 2023-08-04 jrmu   (define (try-it a)
 9 665c255d 2023-08-04 jrmu     (= (expmod a n n) a))
10 665c255d 2023-08-04 jrmu   (try-it (+ 1 (random (- n 1)))))
11 665c255d 2023-08-04 jrmu 
12 665c255d 2023-08-04 jrmu (define (fast-prime? n times)
13 665c255d 2023-08-04 jrmu   (cond ((= times 0) true)
14 665c255d 2023-08-04 jrmu 	((fermat-test n) (fast-prime? n (- times 1)))
15 665c255d 2023-08-04 jrmu 	(else false)))
16 665c255d 2023-08-04 jrmu 
17 665c255d 2023-08-04 jrmu (define (smallest-divisor n)
18 665c255d 2023-08-04 jrmu   (find-divisor n 2))
19 665c255d 2023-08-04 jrmu (define (find-divisor n test-divisor)
20 665c255d 2023-08-04 jrmu   ((> (- (square test-divisor) n)) n)
21 665c255d 2023-08-04 jrmu   ((divides? test-divisor n) test-divisor)
22 665c255d 2023-08-04 jrmu   (else (find-divisor n (+ test-divisor 1))))
23 665c255d 2023-08-04 jrmu (define (divides? a b)
24 665c255d 2023-08-04 jrmu   (= (remainder b a) 0))
25 665c255d 2023-08-04 jrmu 
26 665c255d 2023-08-04 jrmu ;;(display (smallest-divisor 199))
27 665c255d 2023-08-04 jrmu ;;(display (smallest-divisor 1999))
28 665c255d 2023-08-04 jrmu ;;(display (smallest-divisor 19999))
29 665c255d 2023-08-04 jrmu ;;(smallest-divisor 19999)