前言：
自古以来，数学家就被有关素数的问题所吸引，许多人都研究过确定整数是否素数的方法。检测一个数是否素数的一种方法就是找出它的因子；另外还有概率方法。
算法只考虑在实践中的可靠性而不考虑在自然界的真理性表现出数学与工程的不同。这也使得概率方法可以在算法中应用。
方法一：寻找因子
采用一种直接方法，用从2开始的连续整数去检查它们能否整除n。
scheme代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15; 用从2开始的连续整数去检查它们能否整除n
(define (smallest-divisor n)
(find-divisor n 2))
; 如果n不是素数，它必然有一个小于或者等于sqrt n的因子，所以只要在1和sqrt n之间检查因子就可以了，所以时间复杂度是sqrt n
; find-divisor过程可以找出当n不是素数时,n的最小因子
(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)))))
; 检查a是否是b的因子
(define (divides? a b)
(= (remainder b a) 0))
; 检查n是否是素数，n是素数当且仅当它是自己的最小因子
(define (prime? n)
(= n (smallest-divisor n)))
find-divisor的结束判断基于如下事实，如果n不是素数，它必然有一个小于或者等于$\sqrt{n}$的因子。（如果d是n的因子，那么n/d当然也是，而n/d绝不会都大于$\sqrt{n}$）这也意味着该算法在1和$\sqrt{n}$之间检查因子。由此可知，确定是否素数所需的步数将具有$\Theta(\sqrt{n}$)的增长阶。
方法二：费马检查（概率算法）
- 费马小定理：
如果n是一个素数，a是小于n的任意正整数，那么a的n次方与a模n同余。如果n不是素数，那么，一般而言，大部分的a$<$n都不满足上面的关系。
这就引出了费马检查算法：对于给定的整数n，随机任取一个a$<$n饼计算出$a^n$取模n的余数。如果得到的结果不等于a，那么n就肯定不是素数。如果它就是a，那么n是素数的机会就很大。通过检查越来越多的a值，我们就可以不断增加对有关结果的信心。
费马检查的时间复杂度为$\Theta(\log{n}$)
scheme代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17; 计算一个base^exp%m，该过程类似fast-expt，采用连续求平方的方式
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp) (remainder (square (expmod base (/ exp 2) m))
m))
(else (remainder (* base (expmod base (- exp 1) m))
m))))
; n是需要检查的数，a是小于n的任意正整数，如果a^n%n=a，那么n是素数的可能性就很大。从1到(n-1)之间随机取一个数a来进行检测。
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
; 按times次对n进行检测，如果每次检测都成功，那么n就是一个素数
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
- 概率方法：
费马检查其实是一个概率方法，因为能通过费马检查的n只表示他有很大概率是素数，但不能保证就是素数。
存在着一种数为$Carmichael$的数，也同样符合费马检查，但是却不是素数，这样的数在100000000之内有255个，但是如果在计算机求解的过程中，要碰上$Carmichael$数，其概率比宇宙射线导致计算机在执行“正确”算法中出错的机会还有小。
另一方面，如果n对于某个随机选出的a能通过检查，n是素数的机会就大于一半。如果n对于两个随机选择的a能通过检查，n是素数的机会就大于四分之三。
因此，通过用更多随机选择的a值运行这一检查，我们就可以使出现错误的概率减小到所需要的任意程度。
这其实是概率算法的领域。概率素数检查在密码学中有着很重要的应用。虽然完成200位数的因数分解现在在计算机上还是不太容易实现的，但是费马检查可以在几秒钟内判断这么大数的素性。
方法三：Miller-Rabin检查（概率算法）
- $Miller-Rabin$检查：
$Miller-Rabin$检查是在费马检查的基础上改进的，它也可以避开$Carmichael$数。
其原理是如果n是素数，a$<$n，则$a^{n-1}\%n=1$，同时也要检查是否会遇到“1取模n的非平凡平方根”
如果n是非素数的奇数，那么，至少有一半的数a$<$n,按照这种方式计算$a^{n-1}$，将会遇到1取模n的非平凡平方根，所以，在检查的时候，需要检查$n/2$次
$Miller-Rabin$检查也是一个概率算法
$Miller-Rabin$检查的时间复杂度为$\Theta(\log{n}$)
scheme代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29; 非平凡平方根检查。存在a不等于1或者不等于n-1，其平方取模n等于1时，n就不是素数
(define (Nontrivial-square-root? a n)
(and (not (= a 1))
(not (= a (- n 1)))
(= (remainder (square a) n) 1)))
; 计算base^exp % m，同时加入非平凡平方根检查
(define (expmod base exp m)
(cond ((= exp 0) 1)
((Nontrivial-square-root? base m) 0)
((even? exp) (remainder (square (expmod base (/ exp 2) m))
m))
(else (remainder (* base (expmod base (- exp 1) m))
m))))
; 用miller-rabin的方法检查n
(define (miller-rabin-test n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))
; 检查n是否是prime
(define (check-prime n times)
(cond ((= times 0) #t)
((miller-rabin-test n) (check-prime n (- times 1)))
(else #f)))
; 执行n/2次检查如果都通过，就可以保证结果的准确性。
(define (fast-prime? n)
(if (= n 1)
#t
(let ((times (ceiling (/ n 2))))
(check-prime n times))))
