GCD (Greatest Common Divisor) also known as HCF (Highest Common Factor) of two or more integers is the largest positive number which exactly divides each and every input integers.
In Java GCD or HCF can be computed using the following methods:
- Using For Loop
- Using Recursion
- Using Library Function
- Using the Euclidean Algorithm
- Using a Custom Function
In this tutorial, you will learn how to calculate GCD or HCF in Java using for loop, recursion method, Java library function, Euclidean Algorithm, and custom function.
Program to calculate GCD or HCF of two integer
1) Using For Loop and If Statement
//Java program to find GCD using For Loop and If Statement
//Importing the Scanner class of Util Library of java
import java.util.Scanner;
//Main Class of the program
public class Main
{
//Main method of the program
public static void main(String[] args) {
//Creating the object of Scanner Class
Scanner input = new Scanner(System.in);
//Asking Input from user
System.out.print("Enter first number : ");
//Taking input from user
int firstNumber = input.nextInt();
//Asking Input from user
System.out.print("Enter second number : ");
//Taking input from user
int secondNumber = input.nextInt();
//Declaring and initializing the variables
int gcd = 1,i;
//For Loop for iteration to find the GCF of both program
for(i = 1; i <= firstNumber && i <= secondNumber; i++){
/*Checking the modulation with both numbers against
Iteration values
*/
if(firstNumber % i == 0 && secondNumber % i == 0){
//Replacing the gcd value with the higher Iteration value
gcd = i;
}
}
//Printing the output
System.out.printf("GCD for %d and %d is %d",firstNumber,secondNumber,gcd);
}
}
Output:
Enter first number : 88
Enter second number : 80
GCD for 88 and 80 is 8
2) Using Recursion
//Java program to find GCD using Recursion
//Importing the Scanner class of Util Library of java
import java.util.Scanner;
//Main Class of the program
public class Main
{
//Main method of the program
public static void main(String[] args) {
//Creating the object of Scanner Class
Scanner input = new Scanner(System.in);
//Asking Input from user
System.out.print("Enter first number : ");
//Taking input from user
int firstNumber = input.nextInt();
//Asking Input from user
System.out.print("Enter second number : ");
//Taking input from user
int secondNumber = input.nextInt();
/*************
* Declaring and Initilizing a intiger type variable to
* capture the returned value of custom function
**************/
int gcd = getGCD(firstNumber, secondNumber);
//Printing the GCD for the input values
System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);
}
//Crearting a custom function
public static int getGCD(int number1, int number2){
//Checking the second number is not equals to 0
if(number2 != 0)
//If yes,call the function inside the function{Recursion}
return getGCD(number2, number1 % number2);
else
//If false, return the number1
return number1;
}
}
OUTPUT:
Enter first number : 96
Enter second number : 88
GCD of 96, 88 is 8
3) Using Library Function
//Java program to find GCD using Library Function
//Importing the Scanner class of Util Library of java
import java.util.Scanner;
//Importing the math class of java
import java.math.*;
//Main Class of the program
public class Main
{
//Main method of the program
public static void main(String[] args) {
//Creating the object of Scanner Class
Scanner input = new Scanner(System.in);
//Asking Input from user
System.out.print("Enter first number : ");
//Taking input from user and storing it into Biginteger type variable
BigInteger firstNumber = input.nextBigInteger();
//Asking Input from user
System.out.print("Enter second number : ");
//Taking input from user and storing it into Biginteger type variable
BigInteger secondNumber = input.nextBigInteger();
//Geting the GCD of numbers using inbuild function of math library called gcd()
BigInteger gcd = firstNumber.gcd(secondNumber);
//Printing the output
System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);
}
}
OUTPUT:
Enter first number : 96
Enter second number : 80
GCD of 96 , 80 is 16
4) Using the Euclidean Algorithm
//Java program to find GCD using Euclidean Algorithm
//Importing the Scanner class of Util Library of java
import java.util.Scanner;
//Main Class of the program
public class Main
{
//Custom Function
public static int getGCD(int firstNum, int secondNum, int firstCoff, int secondCoff){
if(firstNum == 0){
firstCoff = 0;
secondCoff = 0;
return secondNum;
}
//To store results of recrsive function call
int coff1 = 1, coff2 = 1;
//Recursive call
int gcd = getGCD(secondNum % firstNum, firstNum, coff1, coff2);
//Updating the coff variables for recursive call
firstCoff = coff2 - (secondNum / firstNum) * coff1;
secondCoff = coff1;
//Retun the GCD
return gcd;
}
//Main method of the program
public static void main(String[] args) {
//Creating the object of Scanner Class
Scanner input = new Scanner(System.in);
//Asking Input from user
System.out.print("Enter first number : ");
//Taking input from user
int firstNumber = input.nextInt();
//Asking Input from user
System.out.print("Enter second number : ");
//Asking Input from user
int secondNumber = input.nextInt();
int x = 1, y = 1;
/*************
* Declaring and Initilizing a intiger type variable to
* capture the returned value of custom function
**************/
int gcd = getGCD(firstNumber, secondNumber, x, y);
//Printing the output
System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);
}
}
OUTPUT:
Enter first number : 96
Enter second number : 80
GCD of 96 , 80 is 16
5) Using Custom Function
//Java program to find GCD using Custom Function
//Importing the Scanner class of Util Library of java
import java.util.Scanner;
//Main Class of the program
public class Main
{
//Custom Function
public static int getGCD(int firstNum, int secondNum){
//Integer type variable
int gcd = 1, i;
//For loop for iteration
for(i = 1; i <= firstNum && i <= secondNum; ++i){
//Checking the modulation of both numbers with iteration
//value is equals to 0
if(firstNum % i == 0 && secondNum % i == 0){
//if yes,Update the gcd variable value with iteration value
gcd = i;
}
}
//Returing the gcd;
return gcd;
}
//Main method of the program
public static void main(String[] args) {
//Creating the object of Scanner Class
Scanner input = new Scanner(System.in);
//Asking Input from user
System.out.print("Enter first number : ");
//Taking input from user
int firstNumber = input.nextInt();
//Asking Input from user
System.out.print("Enter second number : ");
//Taking input from user
int secondNumber = input.nextInt();
//Taking the returned value from getGCD Custom Function
int gcd = getGCD(firstNumber,secondNumber);
//Printing the output
System.out.printf("GCD of %d , %d is %d",firstNumber,secondNumber,gcd);
}
}
Output:
Enter first number : 80
Enter second number : 96
GCD of 80 , 96 is 16