Home » Java Programs » Java Basic Programs

Java - Greatest Common Factor or Euclidean Algorithm Program or Highest Common Factor

In this code snippet we will learn how to get Greatest Common Factor in Java, Implementation of Euclidean Algorithm to get Highest Common Factor.

The Euclidean algorithm is used to find the Greatest Common Factor and Highest Common Factor of two numbers. Highest Common Factor is calculated by divide both numbers with their common factor.

Greatest Common Factor / Euclidean Algorithm Program / Highest Common Factor

import java.util.Scanner;
 
public class HCF {
  
    //  greatest common factor
    public static int hcf(int First_number, int Second_number) {
         int hcf=0;
         int min = Math.min(First_number,Second_number);
           
         for(int i=min; i >= 1; i--)
         {
             if(First_number%i == 0 && Second_number%i == 0)
             {
                 hcf = i;
                 break;
             }
         }  
         return hcf;
    }
  
    public static void main(String[] args) {
      
        Scanner sc=new Scanner(System.in);
 
        System.out.print("First Number  :");
        int num1=sc.nextInt();
        System.out.print("Second Number :");
        int num2=sc.nextInt();
 
        System.out.println("Highest Common Factor: " + hcf(num1,num2));
       
    }
}

Output

    First Number  :24
    Second Number :16
    Highest Common Factor: 8

Java Basic Programs »

---