# 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions