素数

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

素数判定的历史

鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找质数公式，到了高斯时代，基本上确认了简单的质数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。 素性判断算法可分为两大类，确定性算法及随机算法。前者可给出确定的结果但通常较慢，后者则反之。详见以下列表。

确定型算法

试除法﹝埃拉托斯特尼筛法﹞

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

卢卡斯-莱默检验法

AKS素数测试

随机算法

费马素性检验

米勒-拉宾检验

欧拉-雅科比测试

参见

素数公式

费马小定理

埃拉托斯特尼筛法

外部链接

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。