# GCD or HCF Program in Java

In the previous program, we developed a Java program to find the lcm (Least or lowest common multiple) of two numbers. Now in this post, we will develop the HCF or GCD program in Java to find the HCF or GCD of two numbers.

The highest common factor (HCF) of two or more numbers is the greatest number which divides each of them exactly. Greatest Common Measure(GCM) and Greatest Common Divisor(GCD) are the other terms used to refer to HCF.

Example: HCF of 60 and 75 = 15 because 15 is the highest number which divides both 60 and 75 exactly.

Procedure to find the HCF or GCD of two numbers,
1) Take two numbers
2) Declare a temporary variable `hcf` to store the HCF value
3) Take an iterator variable and initialize it with 1 i.e. `i=1`
4) Check both numbers are divisible by iterator variable (i) or not?
5) If yes then `hcf = i`
6) Increase the iterator variable by 1
7) Repeat 4 to 6 step until the iterator variable is less than both numbers

``````import java.util.Scanner;

public class HCFProgram {

public static int findHCF(int num1, int num2){

// declare variable to store hcf value
int hcf = 0;
int i = 1;

while(i<=num1 && i<=num2) {
if(num1%i==0 && num2%i==0)
hcf = i;
i++;
}

return hcf;
}

public static void main(String[] args) {

// declare variables
int number1 = 0;
int number2 = 0;
int hcf = 0;

// create Scanner class object
Scanner scan = new Scanner(System.in);

// take input
System.out.print("Enter two integer numbers::");
number1 = scan.nextInt();
number2 = scan.nextInt();

// find HCF of both numbers
hcf = findHCF(number1, number2);

// display HCF value
System.out.println("HCF(" + number1
+ "," + number2 + ") = " + hcf );

// close Scanner class object
scan.close();
}
}``````

Output:-

Enter two integer numbers:: 12 15
HCF(12,15) = 3

Enter two integer numbers:: 900 270
HCF(900,270) = 90

In this HCF program in Java, we have used too many iterations to find the GCD or HCF of two numbers. So, it gives less performance. We can reduce the number of iterations using the below program.

## Another way to find GCD or HCF of two numbers

Procedure to find GCD or HCF of two numbers,
1) Take two numbers
2) find the largest & smallest number among them
3) subtract the smallest number value from the largest number
4) repeat this process until both numbers become equal

``````import java.util.Scanner;

public class HCFProgram {

public static int findHCF(int num1, int num2) {
while(num1 != num2) {
if(num1 > num2)
num1 = num1 - num2;
else
num2 = num2 - num1;
}
return num1;
}

public static void main(String[] args) {

// declare variables
int number1 = 0;
int number2 = 0;
int hcf = 0;

// create Scanner class object
Scanner scan = new Scanner(System.in);

// take input
System.out.print("Enter two integer numbers::");
number1 = scan.nextInt();
number2 = scan.nextInt();

// find HCF of both numbers
hcf = findHCF(number1, number2);

// display HCF value
System.out.println("HCF(" + number1
+ "," + number2 + ") = " + hcf );

// close Scanner class object
scan.close();
}
} ``````

## Java program to find GCD or HCF using LCM

The product of two numbers a and b is equal to the product of HCF(a,b) and LCM(a,b).

``a*b = HCF(a,b) * LCM(a,b)``

In the below GCD or HCF program in java, we first find the LCM of numbers then using the given formula HCF of numbers will be calculated. The Formula used for this purpose is:-

``HCF(a,b) = (a*b) / LCM(a,b)``
``````import java.util.Scanner;

public class HCFProgramUsingLCM {

// method to find HCF of 2 number
// HCF = ( n1*n2 ) / LCM(n1,n2)
private static long findHCF(int num1, int num2){
return (num1*num2) / findLCM(num1, num2);
}

public static long findLCM(int n1, int n2) {

// declare temporary variable to find lcm
long minMultiple = 0;

// find smallest and largest number
int smallest = (n1<n2) ? n1 : n2;
int largest = (n1>n2) ? n1 : n2;

// assign smallest number to minMultiple
minMultiple = smallest;

// loop
while(true) {
if(minMultiple % largest == 0)
return minMultiple;
minMultiple = minMultiple + smallest ;
}
}

public static void main(String[] args) {

// declare variables
int number1 = 0;
int number2 = 0;
long hcf = 0;

// create Scanner class object
Scanner scan = new Scanner(System.in);

// take input
System.out.print("Enter two integer numbers::");
number1 = scan.nextInt();
number2 = scan.nextInt();

// find HCF of both numbers
hcf = findHCF(number1, number2);

// display HCF value
System.out.println("HCF(" + number1
+ "," + number2 + ") = " + hcf );

// close Scanner class object
scan.close();
}
}``````

## GCD or HCF of Two Numbers using Recursion in Java

We can also use the recursion technique to find the GCD or HCF of two numbers. A technique of defining the method/function that contains a call to itself is called the recursion. The recursive function/method allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.

``````import java.util.Scanner;

public class HCFProgramUsingRecursion {

public static int findHCF(int num1, int num2) {
if(num2 == 0) // base case
return num1;
else // general case
return findHCF(num2, num1%num2);
}

public static void main(String[] args) {

// declare variables
int number1 = 0;
int number2 = 0;
long hcf = 0;

// create Scanner class object
Scanner scan = new Scanner(System.in);

// take input
System.out.print("Enter two integer numbers::");
number1 = scan.nextInt();
number2 = scan.nextInt();

// find HCF of both numbers
hcf = findHCF(number1, number2);

// display HCF value
System.out.println("HCF(" + number1
+ "," + number2 + ") = " + hcf );

// close Scanner class object
scan.close();
}
}``````

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!