Euclides Algorithm (GCD)
Program the Greatest Common Divisor/Denominator
In mathematics, the greatest common divisor / denominator (GCD) or greatest common factor (GCF) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 136 and 600 is 8.
Maybe, the first idea that comes to mind to find the GCD is to write a loop that checks every number that is less than the two numbers. The Euclidean Algorithm however is a better way of finding the GCD.
The Euclidean Algorithm: Given two numbers, repeatedly replace the larger number with the greater number mod the lesser number. Keep repeating the step until one of the two numbers reaches zero, the other number will then be the greatest common denominator (or greatest common divisor), the GCD.
GCD(A,B) → B = quotient * A + remainder, where A<=B 