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);
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;
}
}

Dividend : The number which is divided.
Divisor : The number which divides another number.
Remainder : Number which is left as a result of division.
Quotient : Number which is obtained by dividing one digit with another.

For Example, in the division of 13 is divided by 4 (13/4), 13 is the dividend, 4 is the divisor, 1 is the remainder and 3 is the quotient.

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);
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);
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.

0
Liked the article ? Spread the word...