**What is GCD ?**

GCD stands for **G**reatest **C**ommon **D**ivisor. 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.

**How to calculate ?
**

GCD can be calculated in many ways using a java program. Below are listed various approaches:

**Method 1: Repeated Division**

This method works on the following logic:

- Divide larger number by smaller number.
- Divide divisor of previous step with remainder of previous step. That is, the divisor of previous step will be the dividend of next step.
- 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.

**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); // 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. Keep visiting for more such stuff !!!.

0
## Leave a Reply