SICP 1.24

(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) ; prime
(timed-prime-test 90000000020) ; non prime
(timed-prime-test 300000000077) ; prime
(timed-prime-test 300000000078) ; non prime