GCD of Two Numbers Problem

[Bunty12]

Hello everyone,

I'm having trouble understanding the GCD of two numbers in Java. I'm trying to understand the algorithm and code from an online resource but I'm having trouble with the code.

The code provided is:

public static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

I don't understand why the code is written this way or what it is doing. Can anyone provide some insight and explain the code to me?

Thanks!

Edited May 4, 2023 by Phi for All
No advertising, please.

[Genady]

The algorithm uses the fact that if x is GCD of a and b then it is GCD of a and b % a. It looks for the GCD using recursion. For example, take 21 and 15. Look for their GCD.

21 % 15 = 6. Look for GCD of 15 and 6.

15 % 6 = 3. Look for GCD of 6 and 3.

6 % 3 = 0. Aha! Return 3, this is the GCD.

[Endy0816]

Wiki page on modulo operation(%) may be of help too.

https://en.m.wikipedia.org/wiki/Modulo

[wtf]

On 3/28/2023 at 5:04 AM, Bunty12 said:

I'm having trouble understanding the GCD of two numbers in Java. I'm trying to understand the algorithm and code from an online resource but I'm having trouble with the code.

It's the Euclidean algorithm. Study this page and work out some examples by hand to see how it works.

https://en.wikipedia.org/wiki/Euclidean_algorithm

Actually the Wiki page is a little confusing, here's a simpler one I found.

https://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html

Edited May 4, 2023 by Phi for All
commercial link removed by moderator