How to Use Java Program to Find the GCD of Two Numbers

The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF), is the largest number that divides two or more numbers without leaving a remainder. Finding the GCD of two numbers is a common task in mathematics and programming, and it can be efficiently calculated using various algorithms. In this blog post, we’ll explore how to write a simple Java program to find the GCD of two numbers using the well-known Euclidean algorithm.

Understanding the Euclidean Algorithm

The Euclidean algorithm is an ancient method for computing the GCD of two numbers. It works on the principle that the GCD of two numbers a and b is the same as the GCD of b and a % b, where % is the modulus operator (remainder of the division).

The steps involved in the Euclidean algorithm are:

1. Divide the larger number by the smaller number.
2. Replace the larger number with the remainder from the division.
3. Repeat the process until the remainder becomes 0. The last non-zero remainder is the GCD of the two numbers.

Java Program to Find GCD Using Euclidean Algorithm

Let’s write a Java program that uses this algorithm to find the GCD of two numbers.

import java.util.Scanner;

public class GCD {
    
    // Method to compute GCD using the Euclidean algorithm
    public static int findGCD(int a, int b) {
        // Base case: when b becomes 0, the GCD is 'a'
        if (b == 0) {
            return a;
        }
        // Recursive case: call the function with b and a % b
        return findGCD(b, a % b);
    }

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

        // Input two numbers from the user
        System.out.print("Enter the first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = scanner.nextInt();

        // Find and display the GCD
        int gcd = findGCD(num1, num2);
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);
        
        scanner.close();
    }
}

Explanation of the Code

1. Imports and Scanner Setup:
   • The program uses the Scanner class to read user input for two integers.
2. findGCD Method:
   • This method takes two integers a and b and uses the Euclidean algorithm to calculate their GCD.
   • If b becomes zero, the GCD is a (this is the base case).
   • Otherwise, the method recursively calls itself with the values b and a % b (remainder of dividing a by b).
3. Main Method:
   • The main method prompts the user to enter two numbers.
   • It then calls the findGCD method to compute the GCD of the two numbers.
   • Finally, it prints the result.

Example Run

Let’s go through an example of how this program works:

Enter the first number: 56
Enter the second number: 98
The GCD of 56 and 98 is: 14

Explanation of the Example:

• The program first takes the two numbers, 56 and 98, as input.
• It then applies the Euclidean algorithm:
  • 98 % 56 = 42 → Now, GCD(56, 42)
  • 56 % 42 = 14 → Now, GCD(42, 14)
  • 42 % 14 = 0 → The remainder is 0, so the GCD is 14.

Thus, the GCD of 56 and 98 is 14.

Alternative Method: Using Math.gcd (Java 8 and above)

If you’re using Java 8 or a newer version, you can also use the built-in gcd method from the Math class to compute the GCD more easily:

public class GCDUsingMathClass {
    public static void main(String[] args) {
        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();

        // Using Math.gcd to find the GCD
        int gcd = Math.gcd(num1, num2);
        System.out.println("The GCD of " + num1 + " and " + num2 + " is: " + gcd);

        scanner.close();
    }
}

Conclusion

Finding the Greatest Common Divisor (GCD) of two numbers is a common problem in mathematics and programming. The Euclidean algorithm provides an efficient and easy way to calculate the GCD using recursion. In Java, we can implement this algorithm ourselves or use the built-in Math.gcd method if you’re using Java 8 or later.

Whether you choose the recursive method or the built-in method, understanding how GCD works is a valuable skill in problem-solving and algorithm design.