The GCD (Greatest Common Divisor) or HCF (Highest Common Divisor) of two numbers is the largest number to divide them.

For example, the GCD of 20 and 28 is 4, and the GCD of 98 and 56 is 14.

A simple solution is to find all the prime factors of two numbers, and then find the intersection of all factors in the two numbers. Finally, the product of the intersection elements is returned. An effective solution is to use Euclid's algorithm, which is the main algorithm used for this purpose. The idea is that if the smaller number is subtracted from the larger number, the GCD of the two numbers will not change.

JAVA:

// Java program to find GCD of two numbers
class Test
{
	// Recursive function to return gcd of a and b
	static int gcd(int a, int b)
	{
		// Everything divides 0
		if (a == 0)
		return b;
		if (b == 0)
		return a;
	
		// base case
		if (a == b)
			return a;
	
		// a is greater
		if (a > b)
			return gcd(a-b, b);
		return gcd(a, b-a);
	}
	
	// Driver method
	public static void main(String[] args)
	{
		int a = 98, b = 56;
		System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
	}
}

Output: 

GCD of 98 and 56 is 14

A more effective arrangement is to utilize the modulo administrator in the Euclidean calculation.

JAVA

// Java program to find GCD of two numbers
class Test
{
	// Recursive function to return gcd of a and b
	static int gcd(int a, int b)
	{
	if (b == 0)
		return a;
	return gcd(b, a % b);
	}
	
	// Driver method
	public static void main(String[] args)
	{
		int a = 98, b = 56;
		System.out.println("GCD of " + a +" and " + b + " is " + gcd(a, b));
	}
}

Output: 

GCD of 98 and 56 is 14

The time intricacy for the above calculation is O(log(max(a,b))) the inference for this is acquired from the investigation of the most dire outcome imaginable. What we do is we ask what are the 2 least numbers that make 1 stride, those would be (1,1). In the event that we need to expand the quantity of steps to 2 while keeping the numbers as low as possible take the numbers to be (1,2). Likewise, for 3 stages, the numbers would be (2,3), 4 would be (3,5), 5 would be (5,8). So we can see a theme here, for the nth advance the numbers would be (fib(n),fib(n+1)). So the most pessimistic scenario time intricacy would be O(n) where a>= fib(n) and b>= fib(n+1). 

Presently Fibonacci arrangement is a dramatically developing arrangement where the proportion of nth/(n-1)th term draws near (sqrt(5)- 1)/2 which is additionally called the brilliant proportion. So we can see that the time intricacy of the calculation increments directly as the terms develop dramatically thus the time intricacy would be log(max(a,b)).