Find GCD (HCF) of Two Numbers in Java: Euclidean Algorithm

Introduction

Finding the Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is one of the oldest and most important problems in mathematics and computer science. Although a simple brute-force solution exists, the Euclidean algorithm, discovered over 2,000 years ago, solves the same problem dramatically faster and remains the standard approach used in modern software.

The GCD problem is a favorite in coding interviews because it tests whether you can recognize a classic optimization. While the brute-force solution checks every possible divisor, the Euclidean algorithm repeatedly reduces the problem using division and remainders, resulting in an elegant algorithm with logarithmic time complexity.

In this guide, you'll learn the brute-force method, the iterative and recursive Euclidean algorithms, how to calculate the GCD of multiple numbers, and the mathematical insight that makes the Euclidean algorithm so efficient.

What Is GCD (HCF)?

The Greatest Common Divisor (GCD), also called the Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers exactly without leaving a remainder.

For example:

24 → 1, 2, 3, 4, 6, 8, 12, 24
36 → 1, 2, 3, 4, 6, 9, 12, 18, 36

The largest common divisor is:

12

Therefore,

GCD(24, 36) = 12

Real-World Applications

GCD is used in:

• Simplifying fractions

• Cryptography (RSA algorithm)

• Modular arithmetic

• Scheduling repeating events

• Number theory algorithms

Method 1: Brute Force Approach

This is the simplest solution.

Check every number from 1 up to the smaller input and remember the largest divisor common to both numbers.

Java Program

public class GCDBruteForce {

    public static void main(String[] args) {

        int a = 24;
        int b = 36;

        int gcd = 1;

        for (int i = 1; i <= Math.min(a, b); i++) {

            if (a % i == 0 && b % i == 0) {
                gcd = i;
            }
        }

        System.out.println("GCD of " + a + " and " + b + " is: " + gcd);
    }
}

Output

GCD of 24 and 36 is: 12

Step-by-Step Trace

After checking every possible divisor, the largest one found is 12.

Drawback

If the smaller number is one billion, this algorithm may perform up to one billion iterations.

Its performance becomes impractical for large numbers.

Method 2: Euclidean Algorithm (Iterative)

The Euclidean algorithm is the standard and most efficient solution.

Instead of checking every divisor, it repeatedly replaces the larger number with the remainder obtained after division.

Java Program

public class GCDEuclideanIterative {

    public static void main(String[] args) {

        int a = 48;
        int b = 18;

        while (b != 0) {

            int temp = b;
            b = a % b;
            a = temp;
        }

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

Output

GCD is: 6

Step-by-Step Trace

When the remainder becomes 0, the current value of a is the GCD.

Method 3: Euclidean Algorithm (Recursive)

The Euclidean algorithm has a naturally recursive definition.

Java Program

public class GCDEuclideanRecursive {

    static int gcd(int a, int b) {

        if (b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }

    public static void main(String[] args) {

        int a = 48;
        int b = 18;

        System.out.println("GCD is: " + gcd(a, b));
    }
}

Output

GCD is: 6

Recursive Execution

gcd(48,18)

↓

gcd(18,12)

↓

gcd(12,6)

↓

gcd(6,0)

↓

6

This recursive version is widely considered the cleanest implementation of the Euclidean algorithm.

Method 4: Finding GCD of an Array

Sometimes the problem asks for the GCD of multiple numbers.

Fortunately, GCD is associative:

GCD(a,b,c)

=

GCD(GCD(a,b),c)

Java Program

public class GCDOfArray {

    static int gcd(int a, int b) {

        if (b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }

    public static void main(String[] args) {

        int[] numbers = {48, 18, 24, 36};

        int result = numbers[0];

        for (int i = 1; i < numbers.length; i++) {
            result = gcd(result, numbers[i]);
        }

        System.out.println("GCD of the array is: " + result);
    }
}

Output

GCD of the array is: 6

Why It Works

Instead of solving all numbers together, repeatedly compute:

GCD(first, second)

↓

GCD(result, third)

↓

GCD(result, fourth)

↓

...

Eventually, the running result becomes the common divisor shared by every number.

Why the Euclidean Algorithm Works

The key mathematical identity is:

GCD(a,b)

=

GCD(b, a % b)

Why?

Suppose a number divides both a and b.

It must also divide:

a − k × b

for any integer k.

Since:

a % b

=

a − floor(a/b) × b

every common divisor of a and b is also a divisor of the remainder.

Therefore, replacing:

(a,b)

↓

(b,a%b)

does not change the GCD.

The numbers simply become smaller and smaller until one reaches zero.

The remaining number is the answer.

How Java Handles This Internally

Brute Force

Variables:

• a

• b

• gcd

• i

are primitive integers stored on the stack.

No heap allocation occurs.

Iterative Euclidean Algorithm

Only three variables are used:

• a

• b

• temp

Memory usage stays constant throughout execution.

Recursive Version

Each recursive call creates one stack frame.

Since the Euclidean algorithm finishes in very few steps, recursion depth remains extremely small.

Array Version

The array:

int[] numbers

is allocated on the heap.

Each call to gcd() briefly uses the call stack before returning.

Real-Life Analogy

Imagine you have a rectangular floor measuring:

48 ft × 18 ft

You want to cover it with the largest possible square tiles without cutting any tile.

The tile size must divide both dimensions exactly.

The largest such tile is:

6 ft

which is precisely:

GCD(48,18)

The Euclidean algorithm repeatedly reduces the remaining rectangle until only the largest square size remains.

Comparison Table

Best Practices

• Always prefer the Euclidean algorithm over brute force.

• Use the recursive version when a concise implementation is preferred.

• Reuse the same two-number GCD function for arrays.

• Use BigInteger.gcd() when working with integers larger than long.

• Validate input if negative numbers are possible.

Common Mistakes

Using Brute Force for Large Numbers

Checking every divisor becomes extremely slow.

Use the Euclidean algorithm instead.

Incorrect Variable Updates

The iterative version must update variables in the correct order:

int temp = b;
b = a % b;
a = temp;

Changing the order produces incorrect results.

Forgetting the Base Case

The recursive solution must include:

if (b == 0)
    return a;

Without it, recursion never ends.

Confusing GCD and LCM

GCD:

Largest common divisor.

LCM:

Smallest common multiple.

These are different concepts.

Assuming GCD Works Only for Two Numbers

You can compute the GCD of an entire array by repeatedly applying the two-number GCD function.

Expert Tips

A strong interview answer is:

"I use the Euclidean algorithm because the GCD of two numbers doesn't change when replacing (a, b) with (b, a % b). This repeatedly reduces the problem size until the remainder becomes zero, at which point the other number is the GCD. The algorithm runs in O(log(min(a,b))) time, making it dramatically faster than checking every possible divisor."

Explaining why the algorithm works—not just writing the code—is often what distinguishes strong interview answers.

Pros and Cons

Frequently Asked Questions

What is GCD?

The largest positive integer that divides two or more numbers exactly.

Is GCD the same as HCF?

Yes.

GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are different names for the same concept.

Which algorithm is best?

The Euclidean algorithm is the standard solution because it runs in logarithmic time.

Can the Euclidean algorithm be written recursively?

Yes.

return (b == 0) ? a : gcd(b, a % b);

is the canonical recursive implementation.

Can I find the GCD of multiple numbers?

Yes.

Compute the GCD repeatedly across the array.

What is the time complexity of brute force?

O(min(a,b))

What is the time complexity of the Euclidean algorithm?

O(log(min(a,b)))

which is dramatically faster.

Does Java provide a built-in GCD method?

For very large integers, BigInteger provides:

bigInteger1.gcd(bigInteger2)

For primitive integers, you typically implement the Euclidean algorithm yourself.

What are coprime numbers?

Two numbers whose GCD equals 1.

Examples:

8 and 15
14 and 25

Is GCD a common interview question?

Yes.

It is one of the most frequently asked mathematical algorithm questions.

Where is GCD used in real-world software?

It is used in:

• Fraction simplification

• Cryptography

• Modular arithmetic

• Scheduling algorithms

• Number theory

What happens if one number is 0?

By definition:

GCD(a,0) = a

The Euclidean algorithm naturally handles this through its base case.