素性測試
素性測試或素數判定，是檢驗一個給定的整數是否為質數的測試。
素數
[編輯]質數是除了自身和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
}
