Prime number or not program - scheme

There are many different procedures for testing primality of numbers. One way to

test if a number is a prime is to find the number's divisors. If a number n is prime then

n equals the smallest integral divisor of n.

Below procedure tests if a number is a prime based on the above method.

(define (is-prime-help n count) (if (= count 1) #t (if(= (modulo n count) 0) #f (is-prime-help n (- count 1)))))

(define (is-prime n) (if(<>

Another method is related to Fermat’s little theorem:

If n is a prime number and a is any positive integer less than n, then a raised to the

nth power is congruent to a modulo n.

Two numbers are said to be congruent modulo n if they both have the same remainder

when divided by n. Trying a random number a <>, one can be sure that n is not prime

if the remainder of an modulo n is not equal to a. However, the opposite does not

always hold, i.e. a number n is not always prime if the remainder of an modulo n is

equal to a. By trying more and more random a <>, one can get more confident that n

is prime. This algorithm is known as the Fermat test.

Below implements a Fermat test procedure.

(define a 0)

(define (ftp n k) (cond((= k 0) #t) ((= n 2) #t) ((<>

Fermats test is not always accurate as fermat liers can complicate the situation. Modified versions of Fermats test however provide more accurate results.