素数的检测
有两种方法来实现，第一种是寻找因子，思路是：用从2开始的连续整数(在这里自称为检查数)去检查它们是否整除n，根据这个定义过程：
(define (smallest-divisor n)
(find-divisor n 2))
(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)))))
(define (divides? a b) # 检验能否整除
( = (remainder b a) 0)
(define (prime? n) # 程序入口
(= n (smallest-divisor n)))
如果检查数的平方大于n则过程返回n；如不大于则检验检查数是否能整除n，若能整除则返回该检查数，若不能则让检查数加一后进行循环。当prime?为真时n为素数(n是素数当且仅当它是自己的最小因子)
find-divisor的结束判断基于如下事实，如果n不是素数，它必然有一个小于或者等于√￣n的因子，这也意味着该算法只需在1和√￣n之间检查因子，可知该算法的增长阶为θ(√￣n)
第二种用费马检查来实现：
费马小定理：如果n是一个素数，a是小于n的任意正整数，那么a的n次方与a模n同余
思路：对于给定的整数n，随机任取一个a < n并计算出a^n取模n的余数，如果结果不等于a，那么n就肯定不是素数，如果是a，那么a是素数的机会就很大，然后再取一个随机的a并采用同样方式检查，随着检查越来越多的a值，我们就可以越来越增加确认性
# 该过程计算一个数的幂对另一个数取模的结果
(define ( expmod base exp m)
(cond (= exp 0) 1)
(even? exp)
(remainder (square (exmod base ( / exp 2) m))
m))
(else
(remainder (* base (expmod base (- exp 1) m))
m))))
# 返回随机数
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
# 按照times的次数进行检查，若每次都为真，则该过程才返回真
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
