Write a C++ Program to Find GCD.

Write a C++ Program to Find GCD.

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int num1, num2;
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "GCD of " << num1 << " and " << num2 << " is " << result << endl;
    return 0;
}

//===========
OUTPUT:
Enter two numbers: 24 36
GCD of 24 and 36 is 12

Explanation:

The program uses the Euclidean algorithm to find the GCD of two numbers. The function gcd() takes two integer parameters a and b and recursively calculates the GCD by calling itself with b and a%b. This continues until b becomes 0, at which point the function returns a, which is the GCD of the original a and b.

In the main() function, the program prompts the user to enter two integers and stores them in num1 and num2. It then calls the gcd() function with these two numbers and stores the result in result. Finally, it prints the result along with the original input numbers.

Notes:

• GCD is the largest positive integer that divides both of the given numbers without leaving a remainder.
• Euclidean algorithm is an efficient algorithm to find GCD of two numbers. It works by repeatedly dividing the larger number by the smaller number and taking the remainder until the remainder is zero. The GCD is the last non-zero remainder.
• The using namespace std statement is used to avoid writing std:: before every cout and cin statement.
• The endl statement is used to insert a newline character and flush the output buffer, which forces the output to be displayed immediately on the console.