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) ((<>