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