Java Program to Find HCF of Two Numbers

You can find the HCF of two numbers in Java using the Euclidean algorithm with code like while(b != 0) { int temp = b; b = a % b; a = temp; } where a ends as the HCF.

Examples

Inputa = 12, b = 18

Output6

Inputa = 100, b = 25

Output25

Inputa = 7, b = 3

Output1

How to Think About It

To find the HCF of two numbers, think about the largest number that divides both without leaving a remainder. The Euclidean algorithm helps by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the HCF.

Algorithm

1

Get two numbers as input.

2

While the second number is not zero, do:

3

Replace the first number with the second number.

4

Replace the second number with the remainder of the first number divided by the second number.

5

When the second number becomes zero, the first number is the HCF.

6

Return the first number as the result.

Code

java

public class HCF {
    public static void main(String[] args) {
        int a = 12, b = 18;
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        System.out.println("HCF is " + a);
    }
}

Output

HCF is 6

Dry Run

Let's trace the example where a=12 and b=18 through the code.

1

Initial values

a = 12, b = 18

2

First iteration

temp = 18; b = 12 % 18 = 12; a = 18

3

Second iteration

temp = 12; b = 18 % 12 = 6; a = 12

4

Third iteration

temp = 6; b = 12 % 6 = 0; a = 6

5

Loop ends

b is 0, so HCF is a = 6

a	b	temp	a % b
12	18	-	-
18	12	18	12
12	6	12	6
6	0	6	0

Why This Works

Step 1: Using the Euclidean algorithm

The code uses the Euclidean algorithm which finds the HCF by repeatedly replacing the larger number with the remainder of dividing the two numbers.

Step 2: Loop until remainder is zero

The loop continues until the remainder (b) becomes zero, meaning the last non-zero remainder (a) is the HCF.

Step 3: Final result

When the loop ends, the variable a holds the highest common factor of the two input numbers.

Alternative Approaches

Using recursion

java

public class HCF {
    public static int findHCF(int a, int b) {
        if (b == 0) return a;
        return findHCF(b, a % b);
    }
    public static void main(String[] args) {
        System.out.println("HCF is " + findHCF(12, 18));
    }
}

This recursive method is elegant and easy to read but may cause stack overflow for very large inputs.

Using subtraction method

java

public class HCF {
    public static int findHCF(int a, int b) {
        while (a != b) {
            if (a > b) a = a - b;
            else b = b - a;
        }
        return a;
    }
    public static void main(String[] args) {
        System.out.println("HCF is " + findHCF(12, 18));
    }
}

This method uses repeated subtraction and is less efficient than the modulo method but easier to understand for beginners.

Complexity: O(log(min(a,b))) time, O(1) space

Time Complexity

The Euclidean algorithm runs in logarithmic time relative to the smaller input number because each step reduces the problem size significantly.

Space Complexity

The algorithm uses constant extra space since it only stores a few variables and updates them in place.

Which Approach is Fastest?

The modulo-based Euclidean algorithm is faster and more efficient than the subtraction method and safer than recursion for large inputs.

Approach	Time	Space	Best For
Modulo Euclidean Algorithm	O(log(min(a,b)))	O(1)	General use, large numbers
Recursive Euclidean Algorithm	O(log(min(a,b)))	O(log(min(a,b)))	Clean code, small inputs
Subtraction Method	O(min(a,b))	O(1)	Simple understanding, small numbers