質數測試

檢驗一個給定的整數是否為質數的演算法

質數測試質數判定,是檢定一個給定的整數是否為質數的測試。

質數

質數是除了自身和1以外,沒有其它質數因子的自然數。自從歐幾里得證明了有無窮個質數以後,人們就企圖尋找一個可以構造所有質數的公式,尋找判定一個自然數是不是質數的方法。因為質數的地位非常重要。

質數判定的歷史

鑑別一個自然數是質數還是合數,這個問題在中世紀就引起人們注意,當時人們試圖尋找質數公式,到了高斯時代,基本上確認了簡單的質數公式是不存在的,因此,高斯認為對質性判定是一個相當困難的問題。從此以後,這個問題吸引了大批數學家。 質性判斷演算法可分為兩大類,確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢,後者則反之。詳見以下列表。

確定型演算法

  • 試除法(埃拉托斯特尼篩法
    • 嘗試從    的整數是否整除  
// 以 C 語言實現埃拉托斯特尼篩法
// 用以判斷質數的 is_prime 副函式
int is_prime(int x)
{
    if(x < 2) return 0;            // 1 不是質數,且不考慮負整數與 0,故輸入 x<=1 時回傳 0
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0) return 0;    // 一旦出現整除,回傳 0
    return 1;                       // 迴圈跑完後都沒有整除,回傳 1
}
 
  • 費馬質性檢定
  • 米勒-拉賓檢定
  • 歐拉-雅科比測試
    • 對於n,挑選隨機的 ,測試 ,這裡 為雅可比符號。如果N為質數,等式一定成立;如果N為合數,等式有一半的機率不成立。

參見

外部連結