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*

n*th 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 *a**n *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 *a**n *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) ((<>

## No comments:

Post a Comment