0

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

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!!!

Calling code :-

boolean p=prime(BigInteger.valueOf(15));
    System.out.println("P="+p);

Called code :-

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;
}
songyuanyao
  • 169,198
  • 16
  • 310
  • 405
Am_I_Helpful
  • 18,735
  • 7
  • 49
  • 73
  • I assume part of the challenge here is to implement all of the methods from scratch? Hence the square root implementation? – Evan Knowles May 27 '14 at 06:56
  • 3
    I strongly suggest stepping through this with a debugger. I believe you'll find the problem in seconds. – Dawood ibn Kareem May 27 '14 at 06:57
  • The square root of 15 (and most numbers) is not an integer, so your square root function is not going to be able to find a correct answer. For example, for 15 it returns a square root of 2. – Evan Knowles May 27 '14 at 06:58
  • @Evan Knowles -No,prime() method is itself involving the square-root() method;but,I firmly believe that the error is with the square-root() determining method – Am_I_Helpful May 27 '14 at 06:59
  • If you suspect there is a bug in squareroot(), you may run a small function to verify it first. As far as I can see, the way you handle the return value (mid) is not correct. If the while loop is not executed, the return value is ZERO. – Danke Xie May 27 '14 at 07:03
  • @EvanKnowles -Then why it is correctly determining the prime probability of 13 and 31 exact? I disagree with you. – Am_I_Helpful May 27 '14 at 07:03
  • @shekhar - He's right. Believe him. – Dawood ibn Kareem May 27 '14 at 07:05
  • @DankeXie -Actually,this binary-search method approximately determines the nearest square-root integer in small time;hence I have used it.I have tried this thing earlier,got success in case of int's but having problem with the BigInteger's! – Am_I_Helpful May 27 '14 at 07:06
  • 2
    No, @shekhar, try running 15 through your `squareroot` function. It returns 2, no matter whom you believe. – Dawood ibn Kareem May 27 '14 at 07:08
  • 2
    Don't you think it's a bit rude to contradict the two people who have correctly pointed out your error? – Dawood ibn Kareem May 27 '14 at 07:09
  • @DavidWallace -I know it doesn't work;I have myself tried earlier. I am not showing any rudeness,I am as polite as much as I can, but you people are not helping me with the code. I know you are right,but;help me correcting the code by suggesting another approach to find squareroot() rather than pointing out my mistake. – Am_I_Helpful May 27 '14 at 07:12
  • They are doing *exactly* what you asked them to do. From your question: "Please view the code and **help me point out the mistake!!!**" If you would listen to the advice being given to you you would (probably) have a working algorithm by now. – awksp May 27 '14 at 07:13
  • Oh,my way of questioning was incorrect,I apologise for the same. Sorry ALL! – Am_I_Helpful May 27 '14 at 07:21

1 Answers1

3

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.

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.

Dawood ibn Kareem
  • 77,785
  • 15
  • 98
  • 110