How to Find GCD (Greatest Common Divisor) in Java

What is GCD?

The GCD is the largest positive integer that divides both numbers without a remainder. Example: GCD(12, 18) = 6

Solutions

Method 1: Euclidean Algorithm (Iterative)

java

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

// Usage
System.out.println(gcd(12, 18)); // 6
System.out.println(gcd(48, 18)); // 6
System.out.println(gcd(100, 50)); // 50

Method 2: Euclidean Algorithm (Recursive)

java

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

// Usage
System.out.println(gcd(12, 18)); // 6

Method 3: Using Subtraction

java

public static int gcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

// Usage
System.out.println(gcd(12, 18)); // 6

Finding LCM (Least Common Multiple)

LCM can be calculated using GCD: LCM(a, b) = (a × b) / GCD(a, b)

java

public static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

// Usage
System.out.println(lcm(12, 18)); // 36

Did You Know?

The Euclidean algorithm is one of the oldest algorithms still in common use, dating back to 300 BC! It's incredibly efficient with O(log min(a,b)) time complexity.

Pro Tip

The recursive Euclidean algorithm is the most elegant and efficient solution. It's also commonly asked in coding interviews!

Real-World Use Cases

Fractions: Simplifying fractions to lowest terms
Music: Finding common time signatures
Cryptography: RSA encryption algorithm
Scheduling: Finding common intervals

›Short versionOpen if you only have a minute.

Euclid: replace (a, b) with (b, a % b) until b is 0. The answer is a.
The remainder version is logarithmic. Repeated subtraction is linear in the larger value.
gcd(a, 0) is |a|. gcd(0, 0) has no useful answer.
Java % keeps the sign of the dividend. Take a non-negative result before returning.

Greatest common divisor

Find the largest positive integer that divides both inputs.

Working approach

Normalize both inputs, then loop while the remainder is not 0.
Swap by assigning the old b to a and the remainder to b.
Return the absolute value so a negative input does not produce a negative divisor.

Walk the sample

gcd(48, 18)
48 % 18 = 12, continue with (18, 12)
18 % 12 = 6, continue with (12, 6)
12 % 6 = 0, the answer is 6

The trap

Subtraction is the same algorithm only until the numbers are large. And Math.abs(Integer.MIN_VALUE) does not produce a positive int.

java

static int gcd(int a, int b) {
    long x = Math.abs((long) a);
    long y = Math.abs((long) b);
    while (y != 0) {
        long remainder = x % y;
        x = y;
        y = remainder;
    }
    if (x > Integer.MAX_VALUE) {
        throw new ArithmeticException("gcd does not fit in int");
    }
    return (int) x;
}

What should gcd(0, 0) return?

Every integer divides 0, so there is no greatest one. The loop returns 0 if you feed it (0, 0), and 0 is not a divisor you can use.

Reject that pair. gcd(n, 0) for a non-zero n is |n|, which is well defined.

The remainder form is O(log min(|a|, |b|)) time and O(1) space.

Easy to get wrong

Subtracting instead of using the remainder when the inputs can be large.
Returning a negative GCD because the remainder kept a sign.