Greatest common divisor

Question

I try to find the greatest common divisor for two integers. But I don't understand what is wrong with my code:

public class Main {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int a = s.nextInt();
        int b = s.nextInt();

        while (a != 0 | b != 0) {
            if (a >= b) {
                a = a % b;
            } else {
                b = b % a;
            }
        }

        if (a == 0) {
            System.out.println(b);
        } else {
            System.out.println(a);
        }
    }
}

Answer 1

Just change

a != 0 | b != 0

to

a != 0 && b != 0

Because you version will be work even a or b equals 0. But you need to exit from loop when one of them equals 0. && - better than & because in your case you don't need to check right-hand operator if left equals 0

Answer 2

It is easier to calculate the GCD if we understand the core logic. Try to understand what we need to do, and how we are going to do it before implementing the program.

What we are trying to find is the greatest number that divides both a and b.

So the question arises that how we are going to do it. We do a loop just like you did, but for this case, let's initially assume that a is greater than b.

The first step is to start the loop, while the calculation is not finished. The condition in our case is, we have to stop when any one of the two numbers becomes zero.

while (a != 0 && b != 0)
{
    // Do the calculation here.
}

Now we have to write the calculation. We have assumed that a is greater than b or both are equal.

We keep on assigning the remainder of a divided by b to a.

while (a != 0 && b != 0)
{
    a = a % b;
}

This makes the solution only half correct, we will have to deal with the other case, that is when b is greater than a. Why this happens is after some set of iterations, a will become less than b, and that will result in a being set to 0.

So let's do the same solution to the other case, when a is less than b.

while (a != 0 && b != 0)
{
    if (a > b)
        a = a % b;
    else
        b = b % a;
}

And this is what you wanted to achieve. The non-zero value will be the solution.

Let's just not stop here, and see why your current version does not work. You have had this in your condition.

Your condition is:

a != 0 | b != 0

Here, you are using bit-wise operator OR, between two boolean values, which comes to the following. Assume any of a and b is zero.

Case 1:

a != 0 => true
b != 0 => false

true | false => true

Case 2:

a != 0 => false
b != 0 => true

false | true => true

Therefore as you see in the above cases, it continues to loop until both becomes zero, and hence you will always be reported as the GCD is zero.

Hope this helps.