Greatest common factor

Question

I am trying to find the greatest common factor for two integers. But I do not 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 

Since your version will work even a or b is 0. But you need to exit the loop when one of them is 0. & & is better than that because in your case you do not need to check the right operator if the left is 0

Answer 2

It is easier to calculate the GCD if we understand the basic logic. Try to understand what we need to do, and how we will do it before the implementation of the program.

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

So the question is, how do we do this. We make a loop just like you, but for this case, first assume that a is greater than b .

The first step is to start the cycle, and the calculation is not yet complete. The condition in our case is , we must stop when either of the two numbers becomes zero.

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

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

We continue to assign the remainder a divided by b by a .

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

This makes the solution only half correct; we will have to deal with another case, that is, when b is greater than a . Why does this happen after a certain set of iterations, but will become less than b, and this will lead to the fact that a will be set to 0 .

So, we make the same solution for 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. A non-zero value will be a solution.

Let's just not stop here and see why your current version is not working. You had it in your condition.

Your condition:

 a != 0 | b != 0 

Here you use the bitwise OR operator, between the two boolean values, which comes to the next. Assume that 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 go to zero, and therefore, you will always be registered, since the GCD is equal to zero.

Hope this helps.