呂橙，李敏杰

（北京建筑大學計算機系，北京100044）

0 引言

素數(shù)的研究一直是數(shù)論研究的熱點之一，也是計算機等級考試或各類編程競賽?？嫉闹R點之一，尤其是大數(shù)判斷也是密碼學的基礎。素數(shù)的定義：如果一個整數(shù)n 只有1 和n 兩個因子，則p 為素數(shù)，亦稱為質(zhì)數(shù)。合數(shù)的定義：不為素數(shù)的其他數(shù)為合數(shù)。如果n為合數(shù)，則n 必有一個小于或等于n 的平方根的數(shù)因子。素數(shù)的判定方法是對輸入的整數(shù)判定是素數(shù)還是合數(shù)，本文對已有的方法進行梳理，并給出算法模板。

1 算法分析與實現(xiàn)

1.1 樸素判別法

定理1n＞1 是素數(shù)，當且僅當不大于√n的所有素數(shù)都不能整除n。

這種算法是最直接，最簡單的素數(shù)判斷法，又稱為樸素判別法、或試除法，即判斷n 是否為素數(shù)，根據(jù)素數(shù)定義，可以用n 除以從2～n-1 之間所有的數(shù)，如果能整除，則說明不是素數(shù)，否則就是素數(shù)。事實上，試除的范圍可以不用2～n-1，而用2～√n即可。試除法的計算量是O（√nlog22n。

C 語言模板如下：

說明：返回0 代表是合數(shù)，返回1 代表是素數(shù)。

1.2 埃拉托斯特尼（Eratosthenes）篩選法

埃拉托斯特尼篩選法，這個古老的篩選法在構(gòu)造素數(shù)表時，仍然起著很大的作用，給定一個n，要找出不大于n 的所有素數(shù)，可以將1，2，…，n 按自然順序排列好。第一步：刪去第一個未被刪去或圈住的數(shù)；第二步：將第一個未被圈住和刪去的數(shù)圈住，刪去所有這個剛被圈住的數(shù)的倍數(shù)。在執(zhí)行第一次第一步時，是刪除1，第一次執(zhí)行第二步時，圈住2 并刪除2 的倍數(shù)，然后回轉(zhuǎn)重復第二步、…、這樣若干次執(zhí)行第二步直到不大于√n的每個數(shù)都被刪除或圈住為止，這時，被圈住的和剩下來未被刪去和圈住的數(shù)便是不大于n 的全部素數(shù)。

例1 判別7393 是否是素數(shù)1。

解：√7393=85，先用埃拉托斯特尼篩選法找出不大于85 的所有素數(shù)：將1 至85 的數(shù)按自然順序排列好，然后，循環(huán)地執(zhí)行上述第二步直至不大于√85≈9的數(shù)全被刪去或圈住為止。即得85 之下的素數(shù)是2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83。

1 k l 4 n 6 p 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

由上表可以看出，圈住和未被刪去的即為素數(shù)。

C 代碼如下：

1.3 高效判別法

現(xiàn)在讓我們討論一下素數(shù)出現(xiàn)的規(guī)律。當n＞=5時，如果 n 為素數(shù)，那么 n mod 6=1 或 n mod 6=5，即n 一定出現(xiàn)在 6x（x≥1）兩側(cè)2。

稍微證明一下：

當x≥1 時，有如下表示方法：

……，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6（x+1），6（x+1）+1，……

不在 6x 兩側(cè)的數(shù)為 6x+2，6x+3，6x+4，即 2（3x+1），3（2x+1），2（3x+2），它們一定不是素數(shù)，所以素數(shù) n一定出現(xiàn)在6x 的兩側(cè)。

故此，我們只需判斷6 的倍數(shù)兩側(cè)的數(shù)即可。

C 代碼如下：

1.4 費馬小定理

試除法出現(xiàn)之后，一直到16 世紀，期間除了一些特殊的、很局限的素數(shù)判別法外，沒有什么重要的結(jié)果，但到了1640 年，法國數(shù)學家費馬注意到了素數(shù)的一個性質(zhì)，這就是費馬小定理。

定理2費馬小定理。若n 是素數(shù)數(shù)，則對所有不被 n 整除的 a，有 an-1≡ 1（mod n）。

定義、對整數(shù) a＞1，滿足 an≡ a（mod n）的合數(shù) n 稱為底為n 的偽素數(shù)。

定理3對每一個整數(shù)a＞1，有無限多個底為a 的偽素數(shù)。

這樣的偽素數(shù)（合數(shù)）的存在是費馬小定理的逆命題不成立的最合適的例證，是由卡米歇爾首先發(fā)現(xiàn)的，故叫卡米歇爾數(shù)。費馬測試是判斷一個數(shù)是否為素數(shù)的一個基于概率的測試，即不保證所找出的素數(shù)的正確性，但錯誤可能性卻小到可以接受。

費馬測試的具體實現(xiàn)是，對于n，從素數(shù)表中取出任意的素數(shù)對其進行費馬測試，如果取了很多個素數(shù)，n 仍未測試失敗，那么則認為n 是素數(shù)。當然，測試的次數(shù)越多越準確，但一般來講50 次就足夠了。另外，預先構(gòu)造一個包括500 個素數(shù)的數(shù)組，先對n 進行整除測試，將會大大提高通過率。

C 代碼如下：

1.5 歐拉函數(shù)與歐拉篩選

埃拉托斯特尼已經(jīng)很高效了，但是很明顯，埃拉托斯尼算法還是有一定的缺陷的，例如埃拉托斯尼算法中，有的合數(shù)被重復篩除，例如30，2*15 篩了一次，5*6重復篩除。由于任何合數(shù)都能表示成一系列素數(shù)的積。然后利用了每個合數(shù)必有一個最小素因子，每個合數(shù)僅被它的最小素因子篩去正好一次。

C 代碼如下：

1.6 米勒拉賓測試（Miller-Rabin）

在小費馬定理的基礎上有人設計出米勒拉賓隨機素數(shù)測試法，大大的提高檢測素數(shù)的正確性。令n-1=2fm，其中 f 是非負整數(shù)，m 是正奇數(shù)。若 bm≡ 1（mod n）或 b2fm≡ -1（mod n），則 0≤j≤f-1 稱一通過以 b 為基的 Miller-Rabin 測試3。

C 代碼如下：

2 結(jié)語

本文對幾種素數(shù)判斷方法進行了綜述，并給出了C 語言的算法模板，各種算法可以解決實際工作中的一些相關問題，具有一定的實際意義。用C 語言實現(xiàn)的算法模板有助于讀者更好地理解和把握該算法的基本思想和實現(xiàn)過程。