Learn to code with PrepInsta
Check PrepInsta Coding Blogs, Core CS, DSA etc
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
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
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
Login/Signup to comment
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);
}
}
Hey there, Kindly join our Discord server for all the technical and subject related queries.
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);
}
}
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);
}
}
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);
}
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);
}
}
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));
}
}
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 ;
}
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);
}
}
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);
}}