确定BigInteger在Java中是否是Prime [英] Determining if a BigInteger is Prime in Java

问题描述

我正在尝试验证输入的 BigInteger 数字是否是主要数字！

I am trying hands on validation of whether a BigInteger number entered is a Prime Number or not!

但是，它对于较小的数字(如 13,31 )运行良好，但在 15 的情况下会产生错误；将其声明为素数.我无法弄清楚该错误，可能是隐藏在涉及 binary-search ！

But, it is running fine for smaller numbers like 13,31,but it yields error in the case of 15;by declaring it as a Prime. I am unable to figure-out the mistake,probably it is hidden in the squareroot() method approach involving binary-search!

请查看代码并帮助我指出错误！！！

Please view the code and help me point out the mistake!!!

呼叫代码:-

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.这导致它返回算法的上一个迭代的中点；这几乎总是错误的.

Your problem is that you return mid from squareroot without reevaluating it as (low + high) / 2. This causes it to return the midpoint of the previous iteration of the algorithm; which is nearly always wrong.

这样做的结果是您有时会错过一些主要因素.在15的情况下，由于squareroot返回2，因此您会错过寻找3作为质数的机会.在13和31的情况下，没有任何主要因素值得您错过，因此您可以获得正确的结果.

The effect of this is that you sometimes miss some of the prime factors. In the case of 15, because the squareroot returns 2, you miss finding 3 as a prime factor. In the cases of 13 and 31, there are no prime factors for you to miss, so you get the correct result.

这篇关于确定BigInteger在Java中是否是Prime的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！