Finding HCF using Java!!

HCF(Highest Common Factor), also known as GCD(Greatest Common Divisor) is is the largest positive integer that divides each of the numbers without leaving a remainder. It is widely used in various mathematical and practical applications like Fraction Simplification, Number theory, Algorithms etc.

There are different algorithms which can be used to find HCF. The most common among them are Euclidean Algorithm, Prime Factorization and Binary Algorithm. In this article, we will have a look on the iterative approach first to find HCF and then we will see the Euclidean Algorithm approach for efficiency.

The iterative code is as follows:

import java.util.*;

public class Main {

    static int findHCF(int num1, int num2) {
        if (num1 == num2) {
            return num1;
        }

        int smaller = Math.min(num1, num2);
        int hcf = 1;

        for (int i = 2; i <= Math.sqrt(smaller); i++) {
            if (num1 % i == 0 && num2 % i == 0) {
                hcf = i;
            }
        }

        return hcf;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter the first number: ");
        int num1 = sc.nextInt();
        System.out.print("Enter the second number: ");
        int num2 = sc.nextInt();

        int result = findHCF(num1, num2);
        System.out.println("The HCF is " + result);
    }
}

The method uses an iterative approach to find the Highest Common Factor (HCF) of two numbers. It initializes with the smaller of the input numbers and iterates from 2 to the square root of the smaller number, checking for common factors. If a common factor is found, it updates the HCF. The method returns the calculated HCF, providing a straightforward implementation for finding the greatest common divisor. The time complexity of the code is O(sqrt(min(num1, num2))). This is because the loop iterates up to the square root of the smaller of the two input numbers, checking for common factors. The space complexity is O(1) because the method uses a constant amount of extra space regardless of the input size.

Now, we will have a look on Euclidean Algorithm approach. Euclidean Algorithm is a more efficient and widely used method for finding the HCF) of two numbers. It is based on the principle that the HCF of two numbers is the same as the HCF of the smaller number and the remainder when the larger number is divided by the smaller number. The code for the same is:

import java.util.*;

public class Main{

    static int findHCF(int num1,int num2){
        while(num2!=0){
            int temp = num2;
            num2 = num1 % num2;
            num1 = temp;
        }
        return num1;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter the first number: ");
        int num1 =  sc.nextInt();
        System.out.print("Enter the second number: ");
        int num2 =  sc.nextInt();

        int result = findHCF(num1,num2);
        System.out.println("The HCF is " + result);

    }
}

The method implements Euclidean Algorithm to efficiently find the Highest Common Factor (HCF) of two numbers. The algorithm continuously replaces the larger number with the remainder of its division by the smaller number until the remainder becomes zero. The last non-zero remainder is the HCF. The time complexity of the provided method is O(log(min(num1, num2))). The space complexity is O(1).

Comparing the time complexities of both the approaches:

The time complexity of Euclidean Algorithm, O(log(min(num1, num2))), is generally more efficient than O(sqrt(min(num1, num2))). As the numbers increase in size, the logarithmic complexity grows more slowly than the square root complexity. Therefore, in terms of time complexity, Euclidean Algorithm is often preferred over an algorithm with a square root complexity when finding the GCD or HCF of two numbers.

Thank you for reading!!