JAVA program for Highest Common Factor (HCF) of two numbers

HCF can be found by using the Euclidean Algorithm. The Euclidean Algorithm is an efficient algorithm for finding the HCF of two numbers quickly.

We have performed the algorithm using a while loop as well as a recursive method. We would encourage you to use the recursive method if recursion is familiar to you.

Euclidean Algorithm :

Step-1 : If 'A' = 0 then HCF is 'B'. Since zero is divisible by any number.

Step-2 : If 'B' = 0 then HCF is 'A'. Since zero is divisible by any number.

Step-3 : Find the remainder 'R' of 'A' divided by 'B'.

Step-4 : Find the HCF of 'B' and 'R' using the previous step, which gives you the HCF of 'A' and B itself.

This is simplified version of the Euclidean Algorithm. We would encourage you to read the Khan Academy explanation article here.

Programming Approach :

Step-1 : Take input two numbers 'A' and 'B'.

Step-2 : Loop or recurse until 'B' = zero.

Step-3 : Initialize 'A' with 'B'.

Step-4 : Initialize 'B' with ('A' mod 'B').

Step-5 : When 'B' = zero, i.e., 'A' mod 'B' = zero, i.e., 'A' is divisible by 'B' exit loop or terminate recursive function.

Step-6 : 'A' is the HCF.

HCF Code with while loop :

HCF Code with recursive function :