素数有关算法
素数定义
素数也叫质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
如何判断一个数是否为素数
（1）6X算法
证明：令x≥1，将大于等于5的自然数表示如下：
0, 1，2, 3，4, 5，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
可以看到，当数字大于5时，任意自然数num
num%6=1或者 num%6=5
num才有可能为素数，其他情况一定不是素数。
算法代码
//判断是否为素数
public boolean isPrimeNumber(int num){
if(num==2||num==3) return true;
if(((num%6)!=1)&&((num%6)!=5)) return false;
int de= (int) Math.sqrt(num);
for(int i=6;i<=de;i=i+6){
if((num%(i+1))==0||(num%(i+5))==0) return false;
}
return true;
}
（2）米勒-拉宾算法
最小费马定理：
如果n是素数，则(a ^ (n - 1)) % n恒等于1。
算法原理：米勒-拉宾算法就是结合最小费马定理，通过不断判断(a ^ (n - 1)) % n的值是否为1来判断。这是一个概率算法，如果为1，不一定为素数，不为1，则必定是合数。循环判断多次就会让概率变得极为的小。
算法代码
在这里插入代码片
查看15道真题和解析