素性测试
素性测试或素数判定，是检验一个给定的整数是否为质数的测试。
素数
[编辑]质数是除了自身和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
}
