Algorithm for GCD(Greatest Common Divisor) computation
Division-based Programmed:
function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
In the subtraction-based version which was Euclid's original version, the remainder calculation (b := a mod b
) is replaced by repeated subtraction.
function gcd(a, b)
while a ≠ b
if a > b
a := a − b
else
b := b − a
return a