GPY - Euclid's Algorithm for Finding GCD

1. Automate Community
2. Education

In mathematics, the Euclidean Algorithm, or Euclid's Algorithm, is an extremely efficient method for computing the Greatest Common Divisor (GCD) of two numbers, the largest number that divides both without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his treatise "Elements" (c. 300 BC). 

The algorithm starts by dividing the larger of the two numbers by the smaller, then by replacing the larger of the two by the remainder (the algorithm eventually stops when the remainder reaches zero). Since the remainders decrease with every step, and can never be negative, a remainder must eventually equal zero. The final non-zero remainder is the greatest common divisor of the two numbers.

The key advantage of the Euclidean Algorithm is that it can find the GCD efficiently without having to compute the prime factors.

[Information from wikipedia, https://en.wikipedia.org/wiki/Euclidean_algorithm]