GCD: Greatest Common Divisor – the largest integer that divides both m and n evenly.
Euclid’s algorithm (the Euclidean algorithm) has existed since ancient times:
GCD(x, y) = GCD(x, x%y)
x = k*y + b. If d is the GCD of x and y, then d must also divide b, and d is the GCD of x and b, where b = x%y.
Code:

1
2
3
4
5

// GCD
int GCD(int x, int y)
{
   return y == 0 ? x : GCD(y, x % y);
}

The book “Beauty of Programming” discusses time optimizations:

1. The modulo operation involves division, which is relatively expensive.
2. How to optimize for big integers.