http://www.alihk.net/~md/fun/stories/prime/prime.htm 关键字:乌兰现象 赛尔伯格不等式 http://www.csie.nctu.edu.tw/~rjchen/BigPrime.files/show.htm 首先，由质数定理我们知道质数的分布密度：小於或等於n的质数个数约等於n / loge n， 换句话说，当我们任意挑选一个数n，且这个数n是质数的机率约等於1 / loge n； 举例来说，如果任意挑选一个100位数的整数，且挑到的整数又刚好是质数的机率约 为1 / loge 10100 ? 1/230，也就是平均每230次应该会有一个质数。 实际上这个数字可以透过一些筛选的技巧使得次数降低，例如判断是否是 小质数2, 3, 5, 11的倍数来决定要不要成为候选质数，如此一来就可以将次数再降低。 如何检验质数 接着，我们说明如何做质数检验，这里我们将检验通过的候选质数分为两类： 一类是检验通过的候选质数有很大的机率真的是质数但不是绝对的，称为可能质数 (probable prime)；另一类则是检验通过的质数真的就是质数， 称为可证明质数(provable prime)。 以下我们就找第一类可能质数的检验法加以说明。这一类的检验法乍看之下似乎 没有价值，然而由於其执行效率快，且可以透过重复多次的检验使得错误率迅速的 降到很低(如低於10-100)，因此在实际应用上，反而有较高的价值。 检查一个整数是否是质数最直觉的方法就是试除法，把n用小於或等於√n的质数去试除， 如果都无法整除则n是质数，这个方法虽然看起来简单，但执行起来却十分费时， 一般来说当n是10位数时就已经很吃力了，更何况我们要的质数往往都是100位数以上。 1640年法国数学家费马(Fermat)注意到质数的一个性质， 称为费马小定理(Fermat’s little theorem)： [费马小定理] 若n是质数，则对所有与n互质的数a，an-1≡1 (mod n) 实际上当n不是质数的时候，有可能存在这样一个a，使得an-1≡1 (mod n)， 这时候我们称n为基於a的伪质数(base-a pseudoprime)，因此，根据定理的逆方向 设计的质数检验法称为费马检验(Fermat testing)。 -- 爱如果能从0开始 那就能回到过去了... 除非..一开始就是个错误... --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.221.183.224