greatest common divisor Algorithm
The greatest common divisor (GCD) algorithm is a mathematical procedure used to determine the largest positive integer that divides two or more numbers without leaving a remainder. It is an essential concept in number theory and has applications in various fields such as cryptography, computer science, and engineering. The most famous and widely-used GCD algorithm is the Euclidean algorithm, which dates back to the ancient Greek mathematician Euclid's work, "Elements," written around 300 BCE. The algorithm is based on the principle that the GCD of two numbers is the same as the GCD of the smaller number and the remainder when the larger number is divided by the smaller number.
To illustrate the Euclidean algorithm, let's consider two integers a and b, where a > b > 0. The algorithm involves dividing a by b and finding the remainder, r. Then, replace a with b and b with r, and repeat the process until the remainder becomes zero. At this point, the divisor (b) is the GCD of a and b. This method can be implemented using either recursion or iteration, and it can be extended to find the GCD of more than two numbers by applying the algorithm pairwise. The Euclidean algorithm is efficient and fast, making it suitable for use in complex calculations and real-world applications.
// C++ program to find GCD of two numbers
#include <iostream>
// Recursive function to return gcd of a and b
int gcd(int a, int b) {
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
// Driver program to test above function
int main() {
int a = 98, b = 56;
std::cout << "GCD of " << a << " and " << b << " is " << gcd(a, b);
return 0;
}
