素数检测

素数检测常见的做法是从 2 开始逐个加到N，逐个检测能否被N整除，当然以2为单位增加可以减少比较次数，但整体都是多项式运行时间的。

这里介绍的基于费马小定理的费马检查方法（来自于SICP 书中）是对数机运行时间的，但它不保证对所有数给出正确的判断，某些数不是素数但可以逃过费马检查，当然这些数的比例很小，所以这个方法还是可用的。

下面是scheme实现的此算法：

#lang racket
(define (square x)  ;求平方
  (* x x))

(define (expmod base exp m)    ;求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))))

(define (fermat-test n)             ;对给定的数n，进行一次费马检查
  ( let ( (a (+ 1 (random(- n 1)))))
     (= (expmod a n n) a)
  ))

(define (is-prime? n times)             ;对给定的数n，进行times次费马检查，若全通过，我们认为它是素数
  ( cond ((= times 0) true)
         ( (fermat-test n)
            (is-prime? n (- times 1)))
         (else false)))

(is-prime? 199 400)               ;三个检测实例
(is-prime? 1999 400)
(is-prime? 19999 400)

费马小定理是说，对某个素数n，任取小于n的整数a，都满足 a mod n= （ a的n次方） mod n，即a=（a的n次方） mod n

费马检查就是每次随机选一个小于n的数作为a，检测它是否满足上述性质，一共检查times次，全部通过我们认为它是素数。

---

很有趣又简单的小例子，可以开眼界。