Problem 9 - GCD of Two Numbers

🎯 Overview

Write a Java program to find the Greatest Common Divisor(GCD) of two numbers.

Important concepts to be aware of:

• This problem can be solved using Euclidean algorithm by subtraction. This algo says that GCD of two numbers = GCD of difference of the two and the smaller number.
• This problem can also be solved if we keep dividing the bigger number by smaller number, until the remainder is zero. This is a better approach to solve this problem.

I have solved using both approaches below.

🎯 Solving the problem in Java

/**
 * Problem 9: Write a Java program to find the Greatest Common Divisor(GCD) of two numbers.
 */
public class Problem_9 {

  public static void main(String[] args) {

    System.out.println("Enter the first number:");
    Scanner sc = new Scanner(System.in);

    int firstNumber = sc.nextInt();

    System.out.println("Enter the second number:");

    int secondNumber = sc.nextInt();

    System.out.println("GCD is: " + calculateGCD(firstNumber, secondNumber));
    System.out.println("GCD is: " + calculateGCDBetterWay(firstNumber, secondNumber));
  }

  // Also known as Euclidean algorithm by subtraction.
  // This algo says that GCD of two numbers = GCD of difference of the two and the smaller number.
  private static int calculateGCD(int firstNumber, int secondNumber) {

    if (firstNumber == 0) {
      return secondNumber;

    } else if (secondNumber == 0) {
      return firstNumber;

    } else if (firstNumber == secondNumber) {
      return firstNumber;
    }

    if (firstNumber > secondNumber) {
      return calculateGCD(firstNumber - secondNumber, secondNumber);

    } else {
      return calculateGCD(secondNumber - firstNumber, firstNumber);
    }
  }

  // Keep dividing the bigger number by smaller number, until the remainder is zero.
  private static int calculateGCDBetterWay(int firstNumber, int secondNumber) {
    if(firstNumber == 0) {
      return secondNumber;
    }
    return calculateGCDBetterWay(secondNumber % firstNumber, firstNumber);
  }
}

Output:

Enter the first number:
23
Enter the second number:
21
GCD is: 1
GCD is: 1

Process finished with exit code 0

🎯 Github

Code shared in this post can be found here.