素數判斷算法綜述與程序實現

呂橙，李敏杰

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

0 引言

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

1 算法分析與實現

1.1 樸素判別法

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

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

C 語言模板如下：

說明：返回0 代表是合數，返回1 代表是素數。

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

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

例1 判別7393 是否是素數1。

解：√7393=85，先用埃拉托斯特尼篩選法找出不大于85 的所有素數：將1 至85 的數按自然順序排列好，然后，循環地執行上述第二步直至不大于√85≈9的數全被刪去或圈住為止。即得85 之下的素數是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

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

C 代碼如下：

1.3 高效判別法

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

稍微證明一下：

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

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

不在 6x 兩側的數為 6x+2，6x+3，6x+4，即 2（3x+1），3（2x+1），2（3x+2），它們一定不是素數，所以素數 n一定出現在6x 的兩側。

故此，我們只需判斷6 的倍數兩側的數即可。

C 代碼如下：

1.4 費馬小定理

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

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

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

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

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

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

C 代碼如下：

1.5 歐拉函數與歐拉篩選

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

C 代碼如下：

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

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

C 代碼如下：

2 結語

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