Java Programs›Numbers›Find GCD (Euclidean Algorithm)

Find GCD (Euclidean Algorithm) in Java

beginner· Numbers · Number Theory

Problem

The greatest common divisor (GCD) of two numbers is the largest number that divides both of them evenly.

Given two integers, find their greatest common divisor.

Input

48, 18

Output

GCD: 6

Java Program

Java

public class FindGCD {
    public static void main(String[] args) {
        int a = 48, b = 18;
        int gcd = 1;

        for (int i = Math.min(a, b); i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
                break; // largest possible divisor found first, counting downward
            }
        }

        System.out.println("GCD: " + gcd);
    }
}

▶ Run Code

Output

GCD: 6

Core Logic

Trying every possible divisor from the smaller number down to 1, and stopping at the first one that divides both numbers evenly, finds the greatest common divisor directly.

How It Works

1The loop starts at Math.min(a, b), since no divisor of both numbers can be larger than the smaller one.
2i counts downward toward 1, checking each candidate in turn.
3a % i == 0 && b % i == 0 checks whether i divides both numbers evenly.
4The first i that satisfies both conditions is the greatest common divisor, and the loop breaks immediately.

For 48 and 18, the loop counts down from 18 and finds that 6 is the first value dividing both evenly.

💡

Key Point: Starting from the smaller number and counting down guarantees the very first match found is the largest possible common divisor — there's no need to check further once one is found.

Complexity

Time Complexity: O(min(a, b))Space Complexity: O(1)

Why: In the worst case the loop checks every candidate from min(a, b) down to 1, and only a single variable is kept regardless of how large the numbers are.

Key Concepts

for loopmodulo operatorearly exit with break

Approach 2: Euclidean Algorithm

Java

public class FindGCDEuclidean {
    static int gcd(int a, int b) {
        if (b == 0) return a; // base case: b has shrunk to zero, a is the answer
        return gcd(b, a % b); // replace the pair with (b, remainder)
    }

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

▶ Run Code

Output

GCD: 6

Core Logic

Repeatedly replacing the larger number with the remainder of dividing it by the smaller one shrinks the pair down to the answer far faster than checking every candidate divisor.

How It Works

1The base case if (b == 0) return a; fires once the second number reaches zero — at that point, a is the GCD.
2Every other call returns gcd(b, a % b), replacing the pair with the smaller number and the remainder of dividing the two.
3Each step's remainder is always smaller than the previous smaller number, so the pair shrinks quickly toward the base case.
4The recursion mirrors the ancient Euclidean algorithm exactly — no candidate divisors are ever tried.

For 48 and 18: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0), which returns 6.

💡

Key Point: This reaches the answer in just a handful of steps regardless of how large the numbers are, unlike the brute-force version whose cost grows with the smaller number itself.

Complexity

Time Complexity: O(log(min(a, b)))Space Complexity: O(log(min(a, b)))

Why: Each call shrinks the pair at a rate related to the Fibonacci sequence in reverse, so the number of calls — and the stack frames they use — grows logarithmically with the smaller number.

Key Concepts

recursionmodulo operatorbase case

← Previous

Find GCD of Multiple Numbers

Find Largest Prime Factor

Related Programs

Numbersintermediate

Calculate Combination (nCr)

Numbersintermediate

Calculate Permutation (nPr)

Numbersintermediate

Calculate Power Using Recursion

Numbersbeginner

Check Abundant Number

Numbersbeginner

Check Armstrong Number