2. Greatest common pisor

The greatest common pisor (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 pisor, is the greatest positive integer that pides 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) = a
gcd(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 int b)
{
   while (b != 0) {
      unsigned int r = a % b;
      a = b;
      b = r;
   }
   return a;
}

In C++17 there is a constexpr function called gcd() in the header <numeric> that computes the greatest common pisor of two numbers.