euclids gcd Algorithm

Euclid's GCD (Greatest Common Divisor) algorithm is an efficient method for finding the greatest common divisor of two integers, which is the largest positive integer that divides both numbers without leaving a remainder. The algorithm dates back to ancient Greece and is attributed to the mathematician Euclid, who described it in his famous work, "Elements," around 300 BCE. The GCD is a fundamental concept in number theory and has practical applications in areas such as cryptography, computer science, and even music theory. The Euclidean algorithm is based on the principle that the GCD of two numbers does not change if one of the numbers is replaced by the remainder obtained when dividing the larger number by the smaller one. The algorithm starts by dividing the larger number (a) by the smaller number (b) and finding the remainder (r). Then, the smaller number (b) is divided by the remainder (r), and the process is repeated until a remainder of zero is obtained. The last non-zero remainder is the GCD of the two numbers. This process can be easily implemented using recursive or iterative programming techniques, making it a popular choice for computing GCDs in practice.
//
// C++ program to demonstrate Basic Euclidean Algorithm
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/math
// https://github.com/allalgorithms/cpp
//
// Contributed by: Bharat Reddy
// Github: @Bharat-Reddy
//
#include <bits/stdc++.h>
using namespace std;


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

int main()
{
    int a,b;
    cout<<"Enter 2 numbers : ";
    cin>>a>>b;
    int g_c_d = gcd(a,b);
    cout<<"GCD is "<<g_c_d<<endl;
    return 0;
}

LANGUAGE:

DARK MODE: