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.

import java.util.Scanner;

public class JavaGCD {
	public static void main(String args[]){
		int x, y;
		Scanner sc = new Scanner(System.in);
		
		System.out.println("Enter two numbers:");
		x = sc.nextInt();
		y = sc.nextInt();
		
		System.out.println("GCD of " + x + " and " + y + " is " + gcd(x,y));
	}
	
	static int gcd(int x, int y){
		//in case any of them is zero then gcd is zero
		if(x == 0 || y == 0)
		       return 0;
		
		//in case both are equal
		if (x == y)
			return x;
		
		//using euclidean algorithm
		if(x > y)
			return gcd(x - y, y);
		else
			return gcd(x, y - x);
	}
}

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.