Greatest Common Divisor in Java: Solution, Explanation & Practice

Find GCD of two numbers

Problem summary

Write a program that finds the Greatest Common Divisor (GCD) of two numbers using Euclidean algorithm.

Starter code

public class Main {
    public static void main(String[] args) {
        int a = 48;
        int b = 18; // Test case 1
        
        // Find GCD using Euclidean algorithm
        // Print: GCD: <result>
    }
}

Expected output and test cases

GCD(48, 18) = 6
```
GCD: 6
```
GCD(25, 15) = 5
```
GCD: 5
```
GCD(17, 13) = 1
```
GCD: 1
```

Hints

Euclidean: GCD(a,b) = GCD(b, a%b)
Continue until b becomes 0
When b is 0, a is the GCD

Validated solution

Reveal Java solution

public class Main {
    static int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b != 0) {
            int remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println("GCD: " + gcd(48, 18));
    }
}

How to approach the problem

Euclid’s algorithm keeps replacing the larger pair (a, b) with (b, a % b). The common divisors do not change, while the second value gets smaller until it reaches zero.

Approach

Normalize the sign if negatives are allowed.
Compute the remainder before overwriting a.
When b reaches zero, a is the GCD.

Time and space complexity

Time: O(log(min(a, b))). Space: O(1).

Edge cases to test

gcd(0, n) is |n|.
gcd(0, 0) has no conventional positive answer; this program returns 0.

Common mistakes

Replacing a before calculating a % b.
Searching every divisor up to both inputs when Euclid’s algorithm is available.

Follow-up challenge

Use GCD to compute LCM without overflowing the intermediate product.

Related Core Java Basics exercises

Practice all Core Java Basics exercises · Run this idea in the Java compiler