Java program to calculate GCD of two numbers

In this article, we will look at 3 ways to calculate GCD of two numbers with java programs. The numbers will be read as input from the keyboard using java scanner class.
What is GCD ?
GCD stands for Greatest Common Divisor. As its name suggests, a GCD of two or more numbers is the highest number that completely divides all those numbers.
In other words, a number which divides two or more numbers with remainder as zero is called the GCD of those numbers.

Method 1: Repeated Division
This method works on the following logic:

1. Divide larger number by smaller number.
2. Divide divisor of previous step with remainder of previous step. That is, the divisor of previous step will be the dividend of next step.
3. Follow Steps 1 and 2 till the remainder becomes zero.

import java.util.Scanner; 

public class GCDCalculator { 
  public static void main(String[] args) { 
    Scanner scanner = new Scanner(System.in); 
    // read in two numbers 
    System.out.println("Enter first number"); 
    int numberOne = scanner.nextInt(); 
    System.out.println("Enter second number"); 
    int numberTwo = scanner.nextInt(); 
    int gcd = calculateGcdBRepeatedDivision(numberOne, numberTwo); 
    System.out.println("GCD is " + gcd); 
    scanner.close(); 
  } 

  static int calculateGcdByRepeatedDivision(int numberOne, int numberTwo) { 
    //iterate a loop while remainder is not zero 
    while (numberTwo != 0) { 
      //get the remainder of division 
      int remainder = numberOne % numberTwo; 
      // make the divisor of this step as the dividend of next step 
      numberOne = numberTwo; 
      // assign remainder to this variable since this is the divisor 
      //for the next step and it is also the condition of loop 
      numberTwo = remainder; 
    } 
    return numberOne; 
  } 
}

Before going further, reading through the following glossary might help you to better understand the logic.

Method 2 : Repeated Subtraction
This is a pretty easy method in terms of understanding.
In this method, the smaller of two numbers is determined. Then a loop is initiated which checks the condition that smaller number is greater than zero.
In each iteration, the smaller number is decreased by one and it is checked that both the numbers are divisible by this number. As soon as this number completely divides both the input numbers, the loop is terminated.

import java.util.Scanner; 

public class GCDCalculator { 
  public static void main(String[] args) { 
    Scanner scanner = new Scanner(System.in); 
    // read in two numbers 
    System.out.println("Enter first number"); 
    int numberOne = scanner.nextInt(); 
    System.out.println("Enter second number");  
    int numberTwo = scanner.nextInt(); 
    int gcd = calculateGcdByRepeatedSubtraction(numberOne, numberTwo); 
    System.out.println("GCD is " + gcd); 
    scanner.close(); 
  } 

  static int calculateGcdByRepeatedSubtraction(int numberOne, int numberTwo) { 
    // declare a variable to hold lower number and initialize it to first number 
    int lowerNumber = numberOne; 
    // if number two is smaller out of the two, then initialize lower number 
    // to second number 
    if (numberTwo < numberOne) { 
      lowerNumber = numberTwo; 
    } 
    // create a loop till the lower number is greater than 1 
    while (lowerNumber >= 1) { 
      // check of lower number divides both the numbers 
      if (numberOne % lowerNumber == 0 && numberTwo % lowerNumber == 0) { 
        break; 
      } 
      // else decrease the lower number by 1 
      lowerNumber--; 
    } 
    // lower number variable will hold the number which divides both the 
    // input numbers, hence it will be gcd 
    return lowerNumber; 
  } 
}

Method 3 : Using Recursion

This method is recursive variant of Method 1 where successive division is performed and in each step, the divisor is the remainder of previous step and the dividend is the divisor of previous step.
In other words, the divisor of Step 2 is the remainder of Step 1 and the dividend of Step 2 is the divisor of Step 1.

public class GCDCalculator { 
  public static void main(String[] args) { 
    Scanner scanner = new Scanner(System.in); 
    // read in two numbers 
    System.out.println("Enter first number"); 
    int numberOne = scanner.nextInt(); 
    System.out.println("Enter second number"); 
    int numberTwo = scanner.nextInt(); 
    int gcd = calculateGcdRecursively(numberOne, numberTwo); 
    System.out.println("GCD is " + gcd); 
    scanner.close(); 
  } 

  static int calculateGcdRecursively(int numberOne, int numberTwo) { 
    int gcd = numberOne; 
    //condition to terminate recursion 
    if (numberTwo == 0) { 
      return gcd; 
    } 
    //call this method with divisor of previous call as dividend of next 
    //and remainder of previous call as divisor of next 
    gcd = calculateGcdRecursively(numberTwo, numberOne % numberTwo); 
    return gcd; 
  } 
}

Method calculateGcdRecursively receives two arguments. Assume the first argument as the larger of two numbers and second argument as the smaller number which means first argument is the dividend and second is the divisor.

In each recursive call, second argument is the remainder from previous call and first argument is the divisor. Thus the divisor of a step is the remainder from previous step and dividend of a step is the divisor of previous step.
The method returns as soon as the remainder (or the second argument) becomes zero. In such condition, the divisor of last step is the result or the GCD.

Hope this post let you learn something new and useful.