# 1. Introduction

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. The concept of GCD is fundamental in number theory and has applications in areas like cryptography. In this blog post, we will implement a C++ program to compute the GCD of two numbers using Euclid's algorithm.

# 2. Program Overview

1. Take two numbers as input from the user.

2. Use Euclid's algorithm to compute their GCD.

3. Display the GCD.

# 3. Code Program

``````#include <iostream>
using namespace std;

// Recursive function to compute GCD
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}

int main() {
int num1, num2;

// Input two numbers
cout << "Enter two numbers: ";
cin >> num1 >> num2;

// Call gcd function and display result
cout << "GCD of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl;

return 0;
}
``````

### Output:

```Enter two numbers: 56 98
GCD of 56 and 98 is: 14
```

# 4. Step By Step Explanation

1. Euclid's Algorithm: The algorithm is based on the principle that the GCD of two numbers also divides their difference. Therefore, the GCD of 'a' and 'b' (where a > b) is the same as the GCD of 'b' and 'a % b'.

2. Recursive Function: The gcd function computes the GCD recursively. The base case is when b becomes zero; the GCD is a.

3. Main Function: Takes two numbers as input and displays their GCD.

Finding the GCD is a foundational operation, and understanding its algorithm is key to many advanced concepts in computer science and mathematics.