C++ Program to Find the GCD Of Two Numbers

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.