prime.scm

(define (square n)
  (* n n))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp) 
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
(define (fermat-test n times)
  (define (test n)
    (let ((a (random (- n 1))))
    (= (expmod a n n) a)))
  (cond ((= times 0) true)
        ((test n) (fermat-test n (- times 1)))
        (else false)))
(define (divides? a b)
  (= (remainder b a) 0))
(define (smallest-divisor n)
    (define (find-divisor n test-divisor)
      (cond ((> (square test-divisor) n) n)
            ((divides? test-divisor n) test-divisor)
            (else (find-divisor n (+ test-divisor 1)))))
    (find-divisor n 2))
(define (real-prime? n)
 
  (= (smallest-divisor n) n))

(define (prime? n)
  (fermat-test n 100))


(define (tp n)
 (display (prime? n))
 (display "\n")
 (display (real-prime? n)))
(tp 1105)