关于素数常用结论 |
您所在的位置:网站首页 › 数论威尔逊定理 › 关于素数常用结论 |
再需要判定的数比较大时,用枚举法肯定不行的,但目前数学界也没有任何一种又快又准确的判定素数的方法,并且也证明了素数不存在任何一种通项表达式。但作为初等数论中最大的一部分内容,数学家们对素数性质进行了大量研究,并得出很多完美结论,这些结论在素数判定时能起到辅助作用。 1. 威尔逊定理: 若p是素数,则(p-1)!=-1 (mod p) (逆定理也成立) 改定理的逆定理也成立,故可用来判定素数,但其复杂度为O(n),甚至不如试除法。此定理有时用来简化有关阶乘的计算。 2. 欧拉定理: 若gcd(a,m)=1,则aΦ(m)=1 (mod m)。 挺常用的一个定理,证明留坑待填... 3. 费马小定理和伪素数: 若p为素数,则ap-1=1 (mod p)。 即欧拉定理的特例,用的也比较多。 要注意的是该定理的逆命题并不成立,符合该定理的逆命题的合数p称为伪素数,如561就是一个伪素数。 4. 米勒罗宾算法: 若费马小定理的逆命题成立,那就非常好,可以轻松地用前面介绍的快速幂来判定一个数是否为素数。但可惜的是它并不成立,但人们发现,不满足逆命题的数很少,因此只要对a进行重复取值,那么判定结果的正确率能解近100%。因此,出现了这样一种概率性算法--米勒罗宾测试法。 算法实现待填... 很多时候要用到这样的算法,都是因为数据太大,而此时伴随的常常就是高精度和Java。很方便的是Java的BigInteger类提供了该方法的实现,其原型为: boolean isProbablerPrime(int certainty) 如果此时的BigInteger可能为素数,则返回true; 如果一定为合数,则返回false。传入的参数越大,则判断准确率越高,但是花费的时间也越长。这个参数一般取50即可。
|
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |