The greatest common divisor (gcd in short) of two or more non-zero integers, also known as the greatest common factor (gcf), highest common factor (hcf), greatest common measure (gcm), or highest common divisor, is the greatest positive integer that divides all of them. There are several ways the gcd could be computed; an efficient method is Euclid's algorithm. For two integers, the algorithm is:
gcd(a,0) = agcd(a,b) = gcd(b, a mod b)
This can be very simply implemented in C++ using a recursive function:
unsigned int gcd(unsigned int const a, unsigned int const b){ return b == 0 ? a : gcd(b, a % b);}
A non-recursive implementation of Euclid's algorithm should look like this:
unsigned int gcd(unsigned int a, unsigned ...
