# 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, therefore 287 = 91*3 + 14.

-> from the defination, any common divisor of 287 and 91 must also be a divisor of 14,
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 have gcd(91,14)=gcd(14,7), and divide 14 by 7.

-> 14 = 7 · 2 + 0 Because 7 divides 14.
-> Therefore, gcd(287,91) = gcd(91,14) = gcd(14,7) = 7.```

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

1. Take input of two numbers in x and y.
2. find max(x, y) and save to variable ‘a‘.
3. find min(x, y) and save to variable ‘b‘.
4. 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.
5. end the iteration
6. 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

1. Take input of two numbers in x and y.
2. call the function GCD by passing x and y.
3. 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:

### One response to “How to find GCD of two numbers in C++”

1. yogesh says:

how to find GCD(0,3,3,6) => 3
thank you