我正在尝试验证输入的BigInteger数字是否为质数!
但是,对于 13,31 这样的较小数字,它运行良好,但在 15 的情况下会产生错误;通过将其声明为质数。我无法找出错误,可能它隐藏在涉及二分搜索的squareroot()方法方法中!
请查看代码并帮我指出错误!!!
调用代码:-
boolean p=prime(BigInteger.valueOf(15));
System.out.println("P="+p);
调用的代码:-
public static boolean prime(BigInteger bi2){
if(bi2.equals(BigInteger.valueOf(2)) || bi2.equals(BigInteger.valueOf(3)))
{
return true;
}
BigInteger bi,bin;
bin=squareroot(bi2);
for(bi=BigInteger.valueOf(2);bi.compareTo(bin)<=0;bi=bi.add(ONE)){
if(bi2.mod(bi).equals(ZERO))
return false;
else continue;
}
return true;
}
public static BigInteger squareroot(BigInteger bi){
BigInteger low,high,mid=ZERO,two;
low=ONE;
high=bi;
two=BigInteger.valueOf(2);
while(low.compareTo(high)<0)
{
mid =(BigInteger)(low.add(high)).divide(two);
//System.out.println("Low-Mid-High="+low+" "+mid+" "+high);
if(mid.multiply(mid).compareTo(bi)==0)
return mid;
if(mid.multiply(mid).compareTo(bi)>0)
high = mid.subtract(ONE);
else if(mid.multiply(mid).compareTo(bi)<0)
low = mid.add(ONE);
}
return mid;
}
最佳答案
您的问题是您从 squareroot
返回 mid
而不将其重新评估为 (low + high)/2
。这会导致它返回算法上一次迭代的中点;这几乎总是错误的。
这样做的结果是你有时会错过一些主要因素。在 15 的情况下,因为平方根
返回 2,所以您错过了找到 3 作为质因数的情况。在 13 和 31 的情况下,没有任何质因数可供您忽略,因此您会得到正确的结果。
关于java - 在 Java 中确定 BigInteger 是否为素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23882873/