Home » Algorithms

Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM

Here, we are going to learn how to find the GCD (Greatest Common Divisor) of two numbers using Euclid's Algorithm (C++ program)?
Submitted by Ankit Sood, on November 11, 2018

What is GCD?

It is called as a greatest common factor or generally called as a highest common factor (HCF). For example, if we take two numbers 4 and 6 then the factors of these numbers are 1,2,2 and 1,2,3 so the common factors are 2 and 1 and multiplication of these common factors is what we call as gcd of these two numbers which in the above case is 2 X 1 =2 so GCD (4,6) = 2.

Basic Euclidean Algorithm for GCD:

The above algorithm stands on two basic facts which are stated below:

• If we try to decrease the bigger number by subtracting that number by the small then the gcd remains unaffected.
• The base case in our algorithm is when we divide the smaller number and remainder comes out to be zero then our algo stops.

Description: So basically avoid all the brute force approaches we can perform the required task in O(log(min(a,b)) time using Euclid's algorithm which is an optimized approach as compared to the other approaches.

C++ program to find GCD of two numbers using EUCLID'S ALGORITHM

#include<iostream>
using namespace std;

int euclidalgo(int x,int y)
{
	if(x==0)
		return y;
	return euclidalgo(y%x,x);
}

int main()
{
	int a,b;
	
	cout<<"Enter two numbers whose GCD is to be calculated: ";
	cin>>a>>b;
	cout<<"GCD of these numbers is: "<<euclidalgo(a,b)<<endl;
	
	return 0;
}

Output

Enter two numbers whose GCD is to be calculated: 4 6
GCD of these numbers is: 2