Java Program to Find GCD of Two Numbers

1. Introduction

The Greatest Common Divisor (GCD) of two numbers is the largest positive integer that perfectly divides both numbers without leaving a remainder. Calculating the GCD is a fundamental concept in mathematics and has various applications in algorithms and computational mathematics. This blog post will explore a Java program to find the GCD of two numbers using Euclid's algorithm, a popular and efficient method for calculating GCDs.

2. Program Steps

1. Define a method to calculate the GCD using Euclid's algorithm.

2. Read two numbers from the user for which the GCD needs to be found.

3. Call the GCD method with the user-provided numbers.

4. Display the calculated GCD.

5. Close the Scanner object to prevent resource leaks.

3. Code Program

import java.util.Scanner;

public class GCDOfTwoNumbers {
    public static void main(String[] args) {
        // Creating a Scanner object for reading input
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter the first number:");
        int num1 = scanner.nextInt(); // Reading the first number
        System.out.println("Enter the second number:");
        int num2 = scanner.nextInt(); // Reading the second number

        // Calculating and displaying the GCD
        int gcd = findGCD(num1, num2);
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);

        scanner.close(); // Closing the scanner
    }

    // Method to find the GCD of two numbers using Euclid's algorithm
    public static int findGCD(int number1, int number2) {
        if (number2 == 0) {
            return number1; // Base case: if the second number becomes 0, return the first number
        } else {
            return findGCD(number2, number1 % number2); // Recursive call
        }
    }
}

Output:

Enter the first number:
54
Enter the second number:
24
The GCD of 54 and 24 is: 6

Explanation:

1. The program begins by importing the Scanner class, which is used to read two numbers from the user.

2. The findGCD method is defined to calculate the GCD of two numbers using Euclid's algorithm. This method takes two integers as parameters and returns their GCD. It works by recursively reducing the problem using the fact that the GCD of two numbers also divides their difference.

3. Inside the findGCD method, the base case checks if the second number is 0. If so, it returns the first number as the GCD. Otherwise, it makes a recursive call with the second number and the remainder of the first number divided by the second number.

4. After reading the two numbers, the main method calls findGCD with these numbers and prints the result.

5. Finally, the Scanner object is closed to avoid resource leaks.