素性测试

维基百科,自由的百科全书
跳转至: 导航搜索

素数判定,或素性测试,是檢驗一個給定的整數是否為質數的测试。

素数[编辑]

質數是除了自身和1以外,没有其它素数因子的自然数。自从欧几里得证明了有无穷个素数以后,人们就企图寻找一个可以构造所有素数的公式,寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。

素数判定的历史[编辑]

鉴别一个自然数是素数还是合数,这个问题在中世纪就引起人们注意,当时人们试图寻找質数公式,到了高斯时代,基本上确认了简单的質数公式是不存在的,因此,高斯认为对素性判定是一个相当困难的问题。从此以后,这个问题吸引了大批数学家。 質性判斷演算法可分為兩大類,確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢,後者則反之。詳見以下列表。

確定型演算法[编辑]

/*埃拉托斯特尼篩法*/
int is_prime(int x)
{
    int i;
 
    if(x <= 1)/*1不是質數,且不考慮負整數與0,故輸入x<=1時輸出為假*/
    {
        return 0;
    }
 
    for(i = 2; i * i <= x; ++ i)
    {
        if(x % i == 0)/*若整除時輸出為假,否則輸出為真*/
        {
            return 0;
        }
    }
 
    return 1;
}

隨機演算法[编辑]

相关知识[编辑]

如果一个数系Ω中的两个数相加、相减、相乘、相除时,仍然得到一个本数系中的数,则此数系叫做“”,或“有理域”。

当两个中的任何一个中,每一个数也同属于另一个,则称为「两群相等」。(N+X)+(N-X)=2N可以用来解释。

参见[编辑]

外部链接[编辑]