The Euclidean algorithm is an algorithm. It can be used to find the biggest number that divides two other numbers (the greatest common divisor of two numbers).
Euclid solved the problem graphically. He said
Start out with two positive integers m and n.
Note: This pseudocode uses modular arithmetic instead of subtraction. It does the same thing as above, but gets the answer faster.
Precondition: two positive integers m and n
Postcondition: the greatest common integer divisor of m and n
if m < n, swap(m,n) while n does not equal 0 r = m mod n m = n n = r endwhile output m
Iterative (Non-recursive):
int euclid_gcd(int m, int n) { int temp = 0; if(m < n) { temp = m; m = n; n = temp; } while(n != 0) { temp = m % n; m = n; n = temp; } return m; }
Recursive:
int euclid_gcd_recur(int m, int n) { if(n == 0) return m; return euclid_gcd_recur(n, m % n); }