Java Program to find GCD or HCF of two numbers

June 29, 2023

HCF of two numbers in Java

Here, in this section we will discuss HCF of two numbers in java.
GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two numbers is the number which is the largest common factor of both numbers. It is also referred as Greatest Common Factor(GCF), Greatest Common Measure(GCM), Highest Common Divisor(HCD).

We will learn

Method 1: Linear Quest to find HCF
Method 2: Euclidean Algorithm: Repeated Subtraction
Method 3: Recursive Euclidean Algorithm: Repeated Subtraction
Method 4: Modulo Recursive Euclidean Algorithm: Repeated Subtraction
Method 5: Handling Negative Numbers in HCF

Method 1 : Linear Quest

Algorithm

Initialize HCF = 1
Run a loop in the iteration of (i) between [1, min(num1, num2)]
Note down the highest number that divides both num1 & num2
If i satisfies (num1 % i == 0 && num2 % i == 0) then new value of HCF is i
Print value of HCF

Method 1 : Java Code

Run

class Main
{
  public static void main (String[]args)
  {
    int num1 = 36, num2 = 60, hcf=0;

    for (int i = 1; i <= num1 || i <= num2; i++)
      {
     if (num1 % i == 0 && num2 % i == 0)
        hcf = i;
      }

    System.out.println("The HCF: "+ hcf);
  }
}

Output

HCF of 36 and 60 is 12

Method 2 : Repeated Subtraction

Algorithm

Run a while loop until num1 is not equals to num2
If num1>num2 then num1 = num1 – num2
Else num2 = num2 – num1
After the loop ends both num1 & num2 stores HCF

Method 2 : Java Code

Run

class Main
{
  public static void main (String[]args)
  {
    int num1 = 36, num2 = 60, hcf;

    while (num1 != num2)
    {
        if (num1 > num2)
            num1 -= num2;
        else
            num2 -= num1;
    }


    System.out.println("The HCF: "+ num1);
  }
}

Output

HCF of 36 and 60 is 12

Lowest Common Multiple (LCM)

Greatest Common Divisor

Binary to Decimal to conversion

Octal to Decimal conversion

Hexadecimal to Decimal conversion

Method 3 : Repeated Subtraction using Recursion

Algorithm

Checked whether any of the input is 0 then return sum of both numbers
If both input are equal return any of the two numbers
If num1 is greater than the num2 then Recursively call findHCF(num1 – num2, num2)
Else Recursively call findHCF(num1, num2-num1)

Method 3 : Java Code

Run

class Main
{
  public static void main (String[]args)
  {
    int num1 = 36, num2 = 60, hcf;

      hcf = getHCF (num1, num2);
      System.out.println ("The HCF: " + hcf);
  }

  static int getHCF (int num1, int num2)
  {
    // Handles the case when one of the number is 0 (num1) 
    // Check alert above in explanation
    if (num1 == 0)
      return num2;

    // Handles the case when one of the number is 0 (num2)
    // Check alert above in explanation
    if (num2 == 0)
      return num1;

    // base case
    if (num1 == num2)
      return num1;

    // num1 is greater
    if (num1 > num2)
      return getHCF (num1 - num2, num2);

    return getHCF (num1, num2 - num1);
  }
}

Output

HCF of 36 and 60 is 12

Method 4 : Repeated Subtraction with Modulo Operator using Recursion

Algorithm

If b is equals to 0 return a
Else recursively call the function for value b, a%b and return

Method 4 : Java Code

Run

class Main
{
    public static void main (String[]args)
    {
        int num1 = 36, num2 = 60, hcf;

            hcf = getHCF (num1, num2);
            System.out.println ("The HCF: " + hcf);
    }

// This method improves complexity of repeated substraction
// By efficient use of modulo operator in euclidean algorithm
    static int getHCF (int a, int b)
    {
        return b == 0 ? a : getHCF (b, a % b);
    }
}

Output

HCF of 36 and 60 is 12

Method 5 : Handling Negative Numbers in HCF

Algorithm

If any of the number is negative then convert it to positive by multiplying it with -1 as according to the proper definition HCF of two numbers can never be negative.

If b is equals to 0 return a
Else recursively call the function for value b, a%b and return

Method 5 : Java Code

Run

class Main
{
    public static void main (String[]args)
    {
        int num1 = -36, num2 = 60, hcf = 1;

        // if user enters negative number, we just changing it to positive
        // By definition HCF is highest positive number that divides both numbers
        // -144 & 32 : HCF = 16 (as highest num that divides both)
        // -144 & - 32 : HCF = 16 (as highest num that divides both)
            num1 = (num1 > 0) ? num1 : -num1;
            num2 = (num2 > 0) ? num2 : -num2;

            hcf = getHCF (num1, num2);
            System.out.println ("The HCF: " + hcf);
}

// This method improves complexity of repeated substraction
// By efficient use of modulo operator in euclidean algorithm
    static int getHCF (int a, int b)
    {
        return b == 0 ? a : getHCF (b, a % b);
    }
}

Output

HCF of -36 and 60 is 12

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

10 comments on “Java Program to find GCD or HCF of two numbers”

siddeshaob2001
public class GCDorHCF {

public static void main(String[] args) {
// TODO Auto-generated method stub

int n1=36,n2=60,hcf=0;
for(int i=1;i<=n1;i++)
{
for(int j=1;j<=n2;j++)
{
if(n1%i==0 && n2%i==0)
{
hcf=i;
}
}
}
System.out.println(hcf);
}
}

0

Log in to Reply

PrepInsta Support
Hey there, Kindly join our Discord server for all the technical and subject related queries.

1

Log in to Reply

Gyanendra
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scn=new Scanner(System.in);
int n1=scn.nextInt();
int n2=scn.nextInt();

int ans=1;
int div=2;

while(n1>1 && n2>1){

if(n1%div==0){
if(n2%div==0){
ans*=div;
n1=n1/div;
n2=n2/div;
}
else{
n1=n1/div;
}
}
else if(n2%div==0){
n2=n2/div;
}
else{
div++;
}
}
System.out.println(ans);
}
}

0

Log in to Reply
Arab Amer
public class Pract {
static Scanner sc=new Scanner(System.in);

public static void main(String[] args) {
System.out.println(“enter the first number..”);
int n1=sc.nextInt();
System.out.println(“enter the second number..”);
int n2=sc.nextInt();
System.out.println(“enter the third number..”);
int n3=sc.nextInt();
int g=0;
for(int i=1;i<n1;i++) {
if(n1%i==0 && n2%i==0 &&n3%i==0)

g=i;
}
System.out.println(g);

}
}

0

Log in to Reply
Vamsi
public class Main {
public static void main(String[] args) {
int x=12,y=13,hcf=0;
for (int i=1;i<=x;i++){
if(x%i==0){
if(y%i==0){
hcf=i;
}
}
}
System.out.println(hcf);

}

2

Log in to Reply
Ravi Kant
public class HCFTwoNumbers {
public static void main(String args[]){
int a, b, i, hcf = 0;
Scanner sc = new Scanner(System.in);
System.out.println(“Enter first number :: “);
a = sc.nextInt();
System.out.println(“Enter second number :: “);
b = sc.nextInt();

for(i = 1; i <= a || i <= b; i++) {
if( a%i == 0 && b%i == 0 )
hcf = i;
}
System.out.println("HCF of 4given two numbers is ::"+hcf);
}
}

0

Log in to Reply
Kundan
import java.util.*;
class main{
static String findHCF(int num1,int num2){
int max = Math.max(num1, num2);
int min = Math.min(num1, num2);
while (max%min!=0) {
int temp = min;
min = max%min;
max = temp;
}
return “HCF of “+num1+” and “+num2+” is : “+min;
}
public static void main(String[] args) {
int num1 = 36,num2 = 60;
System.out.println(findHCF(num1,num2));
}
}

0

Log in to Reply
Anushka
public static int findHCF(int a , int b)
{
int reminder = -1; int dividend ; int divisor ;
if(a > b ) {dividend = a; divisor = b;}
else {dividend = b; divisor = a;}
while(reminder != 0)
{
reminder = dividend % divisor;
dividend = divisor ;
if(reminder == 0)
return divisor;
divisor = reminder;
}
return divisor ;
}

1

Log in to Reply
Er
import java.util.Scanner;

public class p18 {
public static void main(String[] args) {
//find Hcf(hcd ) of two number:
Scanner s=new Scanner(System.in);
int num1=s.nextInt();
int num2=s.nextInt();
int i,hcf=0;
for( i=1; i<=num1/2 && i<=num2/2;i++){
if(num1%i==0 && num2%i==0){
hcf=i;
}
}
System.out.println("HCF of " +num1 + " and " +num2 + " is :" +hcf);

}
}

2

Log in to Reply
Satendra
public class Main
{
public static void main(String[] args)
{ int n=36,n1=12,hcf=0;
for(int i=1;i<=n||i<=n1; i++){
if(n%i==0&&n1%i==0){
hcf=i;

}
}

System.out.println(hcf);

}}

1

Log in to Reply