Java Program to Find the GCD of Two Numbers

Introduction

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. The GCD is also known as the greatest common factor (GCF) or the highest common divisor (HCD). This guide will walk you through writing a Java program that calculates the GCD of two given numbers using the Euclidean algorithm.

Problem Statement

Create a Java program that:

• Prompts the user to enter two integers.
• Calculates the GCD of the two integers.
• Displays the GCD.

Example:

• Input: 36 and 60
• Output: "The GCD of 36 and 60 is 12"

Solution Steps

1. Read the Two Numbers: Use the Scanner class to take the two integers as input from the user.
2. Calculate the GCD: Implement the Euclidean algorithm to find the GCD of the two numbers.
3. Display the GCD: Print the calculated GCD.

Java Program

// Java Program to Find the GCD of Two Numbers

import java.util.Scanner;

public class GCDCalculator {
    public static void main(String[] args) {
        // Step 1: Read the two numbers from the user
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.print("Enter the first number: ");
            int num1 = scanner.nextInt();
            
            System.out.print("Enter the second number: ");
            int num2 = scanner.nextInt();
            
            // Step 2: Calculate the GCD
            int gcd = findGCD(num1, num2);
            
            // Step 3: Display the GCD
            System.out.println("The GCD of " + num1 + " and " + num2 + " is " + gcd);
        }
    }
    
    // Method to find the GCD using the Euclidean algorithm
    public static int findGCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Explanation

Step 1: Read the Two Numbers

• The Scanner class is used to read two integer inputs from the user. The nextInt() method captures each number.

Step 2: Calculate the GCD

• The findGCD() method implements the Euclidean algorithm to calculate the GCD of two numbers.
• The algorithm works as follows:

1. Divide the first number by the second number.
2. Replace the first number with the second number and the second number with the remainder from the division.
3. Repeat the process until the remainder is 0. The GCD is the last non-zero remainder.

Step 3: Display the GCD

• The program prints the GCD of the two numbers using System.out.println().

Output

Enter the first number: 36
Enter the second number: 60
The GCD of 36 and 60 is 12

Conclusion

This Java program demonstrates how to calculate and display the GCD of two given numbers using the Euclidean algorithm. It covers essential concepts such as loops, arithmetic operations, and user input handling, making it a valuable exercise for beginners learning Java programming.