1.2.6实例：素数检测

素数检测算法一（具有平方根号阶时间复杂度）：用从二开始的连续整数来检查是否能整除要测试的素数。

同时基于以下的事实我们还能够减小时间复杂度：如果n不是素数，那么必然有一个大于1小于$\sqrt{n}$的因子。这样，我们将就能够把时间复杂度从线性阶减小到根号阶。

(define (square x);;用来取平方的过程
  (* x x))
(define (smallest-divisor n);;检测一个素数，用从2开始的整数进行验证
  (find-divisor n 2)
  )
(define (find-divisor n test-divisor);;检测因子,如果因子超界说明是素数，返回本身；如果因子可被整除说明找到了最小因子；如果这个因子测不出来，检测下一个因子
  (cond ((> (square test-divisor) n) n)
        ((divide? test-divisor n) test-divisor)
        (else (find-divisor  n (+ test-divisor 1)))))
(define (divide? test n);;判断是否可以整除的谓词
  (= (remainder n test) 0))
(smallest-divisor 5) ；；测试用例 

素数检测方法二（具有对数阶时间复杂度）：费马检查。这个方法基于以下定理或者事实：

1. 费马小定理：如果一个数n是素数，a是小于n的任意正整数，那么a的n次方与n模n同余(两个数除以n的余数相同)
2. 如果n不是素数，对大部分的a都满足以上的关系。随机选取一个a，如果满足，很大可能是素数；如果不满足；肯定不是素数。检测越多的a，我们对结果就越自信。
3. 快速幂算法（这个算法使得对指数的计算的增长阶变成了对数阶）：如果一个数（n）的幂的指数是偶数，那么这个数是幂的指数的一半再求平方；如果是奇数；那么这个数是n再乘这个数的n-1次幂。通过这样的递归方式，使得对幂的运算变为了对数阶。
4. 对于任意的x,y,m，( ( x mod m ) ( y mod m ) ) mod m=( x y ) mod m。 (三和四是使算法复杂度降低的核心)

(define (square x);;用来取平方的过程
  (* x x))
(define (expmod base exp m);;计算一个数幂对m取模的结果。这里用到了事实3和4，是算法的核心
  (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);;随机选取一个数，对n进行一次素数检测
  (define (try a)
    (= (expmod a n n) a))
  (try (+ 1 (random (- n 1)))));;这里的random是从零开始的（包括0）
;;这里理论上应该是用（expmod a 1 n）与(expmod a n n)进行比较，但实际上（expmod a 1 n）==a,没必要进行多余的计算

(define (fast-prime? n times);;迭代，多次测试，提高置信度
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))
  
(fast-prime? 11  100) ;;测试用例 
  
       

方法二是一种概率算法，概率算法得到的结果只有概率上的正确性。而且还存在一些可以骗过费马检查的整数，但极其罕见，所以费马检查还是很可靠的。