**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
```