Euclidean algorithm is used for calculating greatest common divisor of two given numbers.
Subtraction-based version:
Iteration version:
function gcd(a, b): while(a != b): if(a > b): a := a - b; else: b := b - a; return a;
Recursive version:
function gcd(a, b): if(a > b): return gcd(a - b, b); else if(a < b): return gcd(a, b - a); else: return a;
GCD of 27 and 15:
gcd(27, 15) = ? 27 15 --------------------------- 27 - 15 = 12 15 12 15 - 12 = 3 12 - 3 = 9 3 9 - 3 = 6 3 6 - 3 = 3 3 --------------------------- gcd(27, 15) = 3
Division-based version:
Iteration version:
function gcd(a, b): while(b != 0): t := b; b := a mod b; a := t; return a;
Recursive version:
function gcd(a, b): if(b = 0): return a; else: return gcd(b, a mod b);
GCD of 27 and 15:
gcd(27, 15) = ? 27 15 t ---------------------------------------- 15 27 mod 15 = 6 15 6 15 mod 6 = 3 6 3 6 mod 3 = 0 ---------------------------------------- gcd(27, 15) = 3Python Implementation C++ Implementation Java Implementation C# Implementation