The Euclidean Algorithm recursively calculates the greatest common divisor (GCD) of two integers. It works because GCD(a,b) = GCD(a mod b, b) = GCD(b, a mod b). Each step of the algorithm reduces the size of the numbers by about a factor of 2. The total number of steps required is roughly log(a*b). It is much more efficient than brute force testing all possible divisors up to a+b.

#include <iostream> int calcGCD(const int& a, const int& b) { if (b == 0) return a; int aPrime = a % b; return calcGCD(b, aPrime); } int main() { int aa, bb; std::cout << "Enter two integers for GCD: "; std::cin >> aa >> bb; std::cin.ignore(); std::cout << "Answer: " << calcGCD(aa, bb) << std::endl; std::cin.get(); }

## Recent Comments