Euclidean algorithm
The Euclidian algorithm is an algorithm which can be used to find the greatest common divisor of two numbers. That is, we are looking for the biggest number we can find, that divides both numbers.
What the algorithm looks like in words
Euclid solved the problem graphically. He said
- If you have two distances, AB and CD, and you always take away the smaller from the bigger, you will end up with a distance that measures both of them.
The algorithm in pseudocode
Start out with two numbers a, and b. Let m = a, and n= b
- If m < n, swap the values of m and n
- Calculate r = m - n
- Let m = n and n = r
Repeat, until there is r=0, then the wanted number is in m.
