GCD (HCF) of Two Numbers in Java with Explanation, Euclidean Algorithm, Examples, and Program

GCD (HCF) of Two Numbers in Java

The GCD (Greatest Common Divisor), also known as HCF (Highest Common Factor), of two numbers is the largest number that divides both of them exactly. There are multiple ways to find the GCD, but the most efficient is the Euclidean Algorithm.

Understanding the Euclidean Algorithm

The Euclidean Algorithm is based on a simple rule:

GCD(a, b) = GCD(b, a % b) Repeat until b becomes 0. The remaining value of a is the GCD.

Example

Find GCD of 48 and 18

• GCD(48, 18)
• 48 % 18 = 12 → GCD(18, 12)
• 18 % 12 = 6 → GCD(12, 6)
• 12 % 6 = 0 → GCD(6, 0)

Since the second value becomes 0, the GCD is 6.

Java Program: Using the Euclidean Algorithm

public class GCD {

    // Function to compute GCD
    static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        int num1 = 48;
        int num2 = 18;

        int result = gcd(num1, num2);
        System.out.println("GCD (HCF) of " + num1 + " and " + num2 + " is: " + result);
    }
}

Alternate Version (Using Recursion)

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

Practice Challenges

1. Write a program to find the GCD of three numbers.
2. Print all pairs between 1 and 100 whose GCD is 1 (Co-prime pairs).
3. Modify the program to find both GCD and LCM of two numbers.