Euclidean algorithm

Number theory is pretty cool.

Background

Euclid developed an algorithm to find the greatest common divisor of any two natural numbers.

The brute-force approach would be to find all the factors of two numbers, and then iterate to find the largest common one.

Euclid's algorithm uses the idea of quotients and remainders to efficiently find the greatest common divisor.