# How to find GCD of two numbers in C++

Hello, in this tutorial, we will understand **how to find GCD of two numbers in C++** in various ways.

**Greatest Common Divisor** (GCD) or **Highest Common Factor** (HCF) of two number a and b is the largest number that divides a and b. It is denoted by **GCD(a, b)**.

let’s understand GCD with a simple example

Example : Finding GCD of 24 and 36 24 = 2 × 2 × 2 × 3 × 1 and, 36 = 2 × 2 × 3 × 3 × 1 By compairing each multiplier, we can see that 2 × 2 × 3 are common. Therefore GCD(24,36) = 2 × 2 × 3 = 12

This was the simple approach to find GCD of two numbers. It easy to calculate but, a little bit lengthy in the program. Therefore, we will use Euclid’s approach or (Euclidian Algorithm) to find GCD of two number.

## Euclid’s method for finding GCD

The **Euclidean method** is a technique for quickly finding the **GCD** of two integers.

In Euclid’s method or Algorithm if we need to find GCD(a, b) and if ‘a’ can be represented as **a = bq + r** where ‘**q**‘ is quotient and ‘**r**‘ is remainder. Then, **gcd(a, b) = gcd(b, r)**. same for b.

Example:

Finding gcd(91, 287): -> First apply the division algorithm for 287 and 91, therefore287 = 91*3 + 14. -> from the defination, any common divisor of 287 and 91 must also be a divisor of14, so,d|(287 − 91*3) = 14. -> now, any common divisor of 91 and 14 must also be a divisor of 287. So,gcd(287,91) = gcd(91,14). -> Now, Continuing the process by dividing 91 by 14. so,91 = 14 * 6 + 7. -> now, we havegcd(91,14)=gcd(14,7), anddivide 14 by 7.->14 = 7 · 2 + 0Because 7 divides 14. -> Therefore,gcd(287,91) = gcd(91,14) = gcd(14,7) = 7.

### Algorithm to find GCD of two numbers using iteration

- Take input of two numbers in
**x**and**y**. - find
**max(x, y)**and save to variable ‘**a**‘. - find
**min(x, y)**and save to variable ‘**b**‘. - perform iteration for
**y ≠ 0**

(i) save the value of**a mod b**to ‘**r**‘

(ii) save the value of**b in a**and value of**r to b**. - end the iteration
- print value of
**a**.

### C++ program to find the GCD of two numbers using iteration

#include<iostream> using namespace std; int GCD(int, int); int main(){ int y, x; cout<<"Enter the two numbers: "; cin>>x>>y; cout<<"GCD("<< x <<", "<< y <<") = "<< GCD(x, y); return 0; } int GCD(int x, int y){ int a, b, r; if(x > y){ a = x; b = y; } else{ a = y; b = x; } while(b != 0){ r = a % b; a = b; b = r; } return a; }

**Output: **

Enter the two numbers: 91 287 GCD(91, 287) = 7

### Algorithm to find GCD of two numbers using recursion

- Take input of two numbers in
**x**and**y**. - call the function GCD by passing x and y.
- Inside the GCD function call the GDC function by passing y and x%y (i.e. GCD(y, x%y) with the base case y = 0. means, if y is eqal to zero then return x.

### C++ program: Find GCD using recursion

#include <iostream> using namespace std; int GCD(int, int); int main() { int x , y; cout<<"Enter two number: "; cin>>x>>y; cout<<"GCD("<< x <<", "<< y <<") = "<< GCD(x, y); return 0; } int GCD(int x, int y) { if (y == 0) return x; return GCD(y, x % y); }

**Output: **

Enter two number: 91 287 GCD(91, 287) = 7

**you may also learn: **

## Leave a Reply