;

Java Program to Find HCF or GCD of Two Numbers Using the Euclidean Algorithm and Recursion


Tutorialsrack 23/05/2021 Java

In this Java program, you’ll learn how to find the HCF or GCD of two numbers using the Euclidean algorithm and recursion. 

Java Program to Find HCF or GCD of Two Numbers Using Loops and Library Function

Java Program to Find HCF or GCD of Two Numbers Using Recursion

Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers) is the largest number that divides them both without a remainder.

The algorithm is based on the below facts:

For example, if we want to find the H.C.F. of 60 and 36, we divide 60 by 36. The remainder is 24. Now, we divide 36 by 24 and the remainder is 12. Again, we divide the 24 by 12 and the remainder is 0. Hence, 12 is the required H.C.F.

Here is the code of the program to find the HCF(Highest Common Factor) or GCD (Greatest Common Divisor) using the Euclidean algorithm and recursion.

Java Program to Find HCF or GCD of Two Numbers Using the Euclidean Algorithm and Recursion
// Java Program to Find GCD of Two Numbers Using the Euclidean Algorithm

import java.util.Scanner;

public class JavaPrograms {

	//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 recursive 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;
	    //Return the GCD
	    return gcd;

	  }
	
	public static void main(String[] args) {

		// scanner class declaration
		Scanner sc = new Scanner(System.in);
		// input from the user
		System.out.print("Enter the first number : ");
		int num1 = sc.nextInt();
		// input from the user
		System.out.print("Enter the second number : ");
		int num2 = sc.nextInt();

		int x = 1, y = 1;
        /*************
        * Declaring and Initializing an integer type variable to
        * capture the returned value of the custom function
        **************/
        int GCD = getGCD(num1, num2, x, y);
		
		System.out.print("HCF of " + num1 + " and " + num2 + " is " + GCD);
		
		// closing scanner class(not compulsory, but good programming practice)
		sc.close();

	}
}
Output

Enter the first number : 48

Enter the second number : 18

HCF of 48 and 18 is 6


Related Posts



Comments

Recent Posts
Tags