# Java Program to find GCD or HCF of two numbers

## 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

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

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

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

### 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

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

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

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

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

• 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);

}
}

• 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);

}}