Euclidian algorithm
From Wikipedia, a free encyclopedia written in simple English for easy reading.
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.
[edit] 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.
[edit] 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.
This short article can be made longer. You can help Wikipedia by adding to it.
