Java Program to Find GCD of Two Numbers

The GCD (Greatest Common Divisor), also known as HCF (Highest Common Factor), is the largest number that divides two numbers without leaving a remainder.

In this tutorial, we will create a Java program to find the GCD of two numbers using the Euclidean algorithm.

By the end of this guide, you will understand how iterative logic and modulus operations are used in efficient mathematical problem solving.

Concept Overview

The Euclidean algorithm is based on the principle that GCD(a, b) = GCD(b, a % b).

We repeatedly replace the larger number with the remainder until the remainder becomes zero.

Program

import java.util.Scanner;

public class GCDOfNumbers {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter first number: ");
        int a = sc.nextInt();

        System.out.print("Enter second number: ");
        int b = sc.nextInt();

        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }

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

Output

Enter first number: 48
Enter second number: 18
GCD is: 6

Detailed Explanation

The program starts by taking two numbers as input from the user.

It uses a while loop to repeatedly apply the Euclidean algorithm.

In each iteration, the second number becomes the remainder of the division.

The process continues until the second number becomes zero.

At that point, the first number contains the GCD.

Example Walkthrough

Let us consider 48 and 18.

Step 1: 48 % 18 = 12 → (48, 18) becomes (18, 12)

Step 2: 18 % 12 = 6 → (18, 12) becomes (12, 6)

Step 3: 12 % 6 = 0 → GCD = 6

Applications

GCD is used in simplifying fractions, cryptography, and number theory problems.

Advantages of This Approach

This method is highly efficient compared to checking all divisors.

It reduces computation time significantly for large numbers.

Limitations

The program assumes valid integer inputs only.

Improvements You Can Make

You can extend this program to compute LCM using the relation LCM(a, b) = (a × b) / GCD.

You can also implement a recursive version of the Euclidean algorithm.

This Java program builds a strong foundation in mathematical algorithms and efficient problem solving.