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