How to find HCF (highest common factor) of at most 3 numbers in Java

Hi people ! today we are going to see how to find the highest common factor (HCF) also known as the greatest common divisor (GCD) for 2 or 3 numbers. As we all know the highest common factor is the largest or highest number which divides the given number and leaves zero remainders. So let’s start learning how to find HCF of at most 3 numbers in Java.

HCF (highest common factor) of at most 3 numbers in Java

Here we are going to use to long division method to find the HCF or GCD of given numbers in two ways-

  1. Naive method (regular method)
  2. Recursive Method

Both methods are pretty simple to understand. In long division method, the bigger number is divided by other smaller number if the remainder is zero we will print smaller number else the smaller number will become larger and the remainder will become the small number. This process is continued until the remainder is not 1.

For example:-  7 & 21 where small=7 big=21…if  big% small==0 , print small.

Another example:- 24 & 36 where big=36 small=24 remain=36%24==12(not zero)
change small=remain, big=small, loop goes till remain==0.

Here is the code for the same.

import java.util.Scanner;

public class Hcf {
  public static void main(String[] args)
  {
    Scanner sc=new Scanner(System.in);
    System.out.println("enter 1st number");
    int num1=sc.nextInt();
    System.out.println("enter 2nd number");
    int num2=sc.nextInt();
    System.out.println("enter 3rd number (if there is no 3rd number simply enter 0)");
    int num3=sc.nextInt();

    int big=0,small=0;
    if(num1<num2)
    {   big=num2;
    small=num1;
    }
    else 
    {
      big=num1;
      small=num2;
    }

    System.out.println("result through recursive method = " + hcf(big,small,num3));
    NONrecHCF(big,small,num3);

  }
  static int hcf(int big , int small , int num3)  //with recursionn  
  {  
        if(big % small == 0 && num3 % small==0)	  //base case 
    return small;
  else
    return hcf(small , big %small , num3); 
  }

  static void NONrecHCF(int big ,int small ,int num3)
  {
    int remain = 0;
    remain = big % small;
    while(remain!=0)
    {    
      big = small;
      small = remain;
      remain = big % small ;
    }
    if(num3 % small==0) // if third number divides by resultant small then hcf is small
      System.out.println("result through naive method = "+ small);
  }
}
enter 1st number
25
enter 2nd number
10
enter 3rd number (if there is no 3rd number simply enter 0)
0
result through recursive method = 5
result through naive method = 5

Hope you understand the code to find HCF of at most 3 numbers in Java.

You may also read:

Leave a Reply

Your email address will not be published. Required fields are marked *