Online Tutorials & Training Materials | STechies.com
Register Login

Java program to calculate GCD of two numbers

|| 0

Java program to calculate GCD of two numbers
Stechies

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