How to calculate GCD in java / Various ways of GCD calculation in java / Java program to calculate GCD

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.

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:

  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.

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

Mark Your Impression

  Subscribe  
Notify of
Close Menu

Never Miss an article !

Get the new post delivered straight into your inbox, enter your email and hit the button

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

codippa will use the information you provide on this form to be in touch with you and to provide updates and marketing.