(use srfi-19)
(use srfi-27)
(define (timed-prime-test n)
(define (start-prime-test n start-time)
(if (fast-prime? n 10000)
(report-prime start-time)))
(define (report-prime start-time)
(display " *** ")
(display (time-difference (current-time) start-time)))
(define (fast-prime? n times)
(cond ((= times 0) #t)
((fermat-test n) (fast-prime? n (- times 1)))
(else #f)))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random-integer (- n 1)))))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp) (modulo (square (expmod base (/ exp 2) m)) m))
(else (modulo (* base (expmod base (- exp 1) m)) m))))
(define (square n)
(* n n))
(display n)
(start-prime-test n (current-time)))
(timed-prime-test 90000000019)
(timed-prime-test 90000000020)
(timed-prime-test 300000000077)
(timed-prime-test 300000000078)