Euclidean Algorithm(GCD)

Greatest Common Divisor can easily be calculated easily using Euclidean Algorithm.

This is the non recursive pseudo code

function gcd(a, b) while b ≠ 0 t := b b := a mod b a := t return a

int gcd(int a, int b) { if (a == 0) return b; while (b != 0) if (a > b) a = a - b; else b = b - a; return a; }

This is the recursive pseudo code

function gcd(a, b) if b = 0 return a else return gcd(b, a mod b)

int gcd(int a, int b) { if (b==0) return a; else return gcd(b, a%b); }