当需要进一步判定的数较大时，用列举法是绝对不行的，但目前数学界没有快速准确的判定素数的方法，这也证明素数不存在一般项公式。 但作为初等数论的最大部分，数学家们对素数的性质进行了大量的研究，得出了许多完美的结论。 这些结论在素数判定时有辅助作用。
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. zgdxy算法：
如果费马小定理的逆命题成立，那就很好了，用前面介绍的快速乘方就可以很容易判定一个数是否为素数。 但是很遗憾，虽然那个不能成立，但是因为不满足逆命题的数量很少，所以如果重复a取值的话，判定结果的正确率会接近100%。 于是，出现了这样的概率算法--zgdxy测试法。
算法实现.
大多数情况下，使用这样的算法是因为数据太大，伴随而来的常常是高精度和Java。 方便的是，Java的BigInteger类提供了此方法的实现，其原型如下：
布尔可编程序(int certainty )如果此时的BigInteger可能是素数，则为true； 如果一定是正数，则返回false。 传递的参数越大，判断精度越高，但也需要时间。 这个参数通常取50即可。
转载于：https://www.cn blogs.com/frank Chen 831 x/p/10826571.html