«

»

Jul 22

Euclidean Algorithm

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();
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>