如何快速記憶100以內的質數(2)
素性檢測
素性檢測一般用于數學或者加密學領域。用一定的算法來確定輸入數是否是素數。不同于整數分解，素性測試一般不能得到輸入數的素數因子，只說明輸入數是否是素數。大整數的分解是一個計算難題，而素性測試是相對更為容易(其運行時間是輸入數字大小的多項式關系)。有的素性測試證明輸入數字是素數，而其他測試，比如米勒 - 拉賓(Miller–Rabin )則是證明一個數字是合數。因此，后者可以稱為合性測試。質數是因數只有1和它本身的數。
素性測試通常是概率測試(不能給出100%正確結果)。這些測試使用除輸入數之外，從一些樣本空間隨機出去的數;通常，隨機素性測試絕不會把素數誤判為合數，但它有可能為把一個合數誤判為素數。誤差的概率可通過多次重復試驗幾個獨立值a而減小;對于兩種常用的測試中，對任何合數n，至少一半的a檢測n的合性，所以k的重復可以減小誤差概率最多到2^{-k}，可以通過增加k來使得誤差盡量小。
隨機素性測試的基本結構：
1.隨機選取一個數字a。
2.檢測某個包含a和輸入n的等式(與所使用的測試方法有關)。如果等式不成立，則n是合數，a作為n是合數的證據，測試完成。
3.從1步驟重復整個過程直到達到所設定的精確程度。
在幾次或多次測試之后，如果n沒有被判斷為合數，那么我們可以說n可能是素數。
常見的檢測算法：費馬素性檢驗(Fermat primality test)，米勒拉賓測試(Miller–Rabin primality test) ，Solovay–Strassen測試(Solovay–Strassen primality test)，盧卡斯-萊默檢驗法(英語：Lucas–Lehmer primality test)。
質數與素數的區別
質數又稱素數。指在一個大于1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。換句話說，只有兩個正因數(1和自己)的自然數即為素數。比1大但不是素數的數稱為合數。1和0既非素數也非合數。合數是由若干個質數相乘而得到的。
所以，質數是合數的基礎，沒有質數就沒有合數。這也說明了前面所提到的質數在數論中有著重要地位。歷史上曾將1也包含在質數之內，但后來為了算術基本定理，最終1被數學家排除在質數之外，而從高等代數的角度來看，1是乘法單位元，也不能算在質數之內，并且，所有的合數都可由若干個質數相乘而得到。
質數表
質數表的質數又稱素數。指整數在一個大于1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。換句話說，只有兩個正因數(1和自己)的自然數即為素數。比1大但不是素數的數稱為合數。1和0既非素數也非合數。素數在數論中有著很重要的地位。
用6(6N^2+6N)為界劃分成一個個區間，素數的分布規律就明確顯視出來了。隨著區間的增大，素數的個數以波浪的形式漸漸增多。
猜你喜歡：
如何快速記憶100以內的質數(2)
