Loading AI tools
檢驗一個給定的整數是否為質數的演算法 来自维基百科,自由的百科全书
素性测试或素数判定,是檢驗一個給定的整數是否為質數的测试。
質數是除了自身和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
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.