Java Program to Find GCD of Two Numbers Using Euclidean Algorithm

Here you will get java program to find gcd of two numbers using recursion and euclidean algorithm.

Greatest Common Division (GCD) of two numbers is largest number that divides both of them completely. GCD is also called as Highest Common Factor (HCF). There are various ways to find GCD but Euclidean Algorithm is the most efficient way.

Euclid’s algorithm

GCD of two numbers a and b can be obtained by following algorithm.

gcd (a, b) = gcd (a – b, b), if a > b

gcd (a, b) = gcd (a, b – a), if b > a

Example:

To compute gcd (48, 18) first divide 48 by 18 to get quotient as 2 and remainder as 12. Then divide 18 by 12 to get quotient as 1 and remainder as 6. Then divide 12 by 6 to get remainder as 0, which means that 6 is the gcd.

Java Program to Find GCD of Two Numbers

Now lets implement this algorithm recursively to find gcd in Java.

Output

Enter two numbers:
48
18
GCD of 48 and 18 is 6

Comment below if you have any queries related to above program to find gcd of two numbers in Java.

One comment

Leave a Reply

Your email address will not be published. Required fields are marked *