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!

Search