Program to Find the Highest Common Factor (HCF) in Java

Highest Common Factor (HCF)

The Highest Common Factor (HCF) of two numbers is the largest number that divides both of them without leaving a remainder. For example, the HCF of 36 and 60 is 12.

We will explore three different methods to find the HCF of two numbers using Java programming.

Method 1: Using Euclidean Algorithm

We use the Euclidean algorithm, which repeatedly replaces the larger number with its remainder when divided by the smaller number, until the remainder becomes zero.

import java.util.Scanner;

public class HCF_Euclidean {
    public static int findHCF(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("HCF of " + num1 + " and " + num2 + " is " + findHCF(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 36
Enter second number: 60
HCF of 36 and 60 is 12

Method 2: Using Prime Factorization

In this method, we find all prime factors of both numbers and take the product of the common ones.

import java.util.Scanner;

public class HCF_PrimeFactorization {
    public static int min(int a, int b) {
        return (a < b) ? a : b;
    }

    public static int findHCFPrimeFactorization(int a, int b) {
        int hcf = 1;
        for (int i = 2; i <= min(a, b); i++) {
            while (a % i == 0 && b % i == 0) {
                hcf *= i;
                a /= i;
                b /= i;
            }
        }
        return hcf;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("HCF of " + num1 + " and " + num2 + " is " + findHCFPrimeFactorization(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 36
Enter second number: 60
HCF of 36 and 60 is 12

Method 3: Using Recursion

We can also find HCF using recursion, following the Euclidean algorithm.

import java.util.Scanner;

public class HCF_Recursion {
    public static int findHCFRecursive(int a, int b) {
        if (b == 0)
            return a;
        return findHCFRecursive(b, a % b);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter first number: ");
        int num1 = scanner.nextInt();
        System.out.print("Enter second number: ");
        int num2 = scanner.nextInt();
        
        System.out.println("HCF of " + num1 + " and " + num2 + " is " + findHCFRecursive(num1, num2));
        scanner.close();
    }
}
            

Output:

Enter first number: 36
Enter second number: 60
HCF of 36 and 60 is 12