Algoritmo para calcular el máximo común divisor

dados dos números, obtener el máximo número que divida a ambos.
Para ello, lo primero que había que hacer era descomponer cada número en factores primos. Por ejemplo, para calcular el mcd (máximo común divisor) de 756 y 1617:

756 = 7 * 3^3 * 2^2
1617 = 11 * 7^2 * 3

A continuación tomamos los factores comunes elevemos al menos exponente y ese es el mcd; en nuestro ejemplo:

mcd(756,1617) = 7 * 3 = 21

Hacer esto es relativamente sencillo, ahora bien, programarlo ya es otra cosa bien distinta. Lo más complicado sería implementar una función que descomponga un número en sus factores primos.
Se podría hacer, si bien existe un método bastante más sencillo: utilizando el algoritmo de Euclides. ¿En qué consiste? De forma resumida, el pseudocódigo para la función que calcula el mcd quedaría:

function mcd(a, b) {
if (a > b) {
return mcd(a-b, b);
} else if (b > a) {
return mcd(a, b-a);
} else { // a == b
return a;
}
}

Aplicándolo a nuestro ejemplo:

mcd(756,1617) = mcd(756,861) = mcd(756,105) = mcd(651,105) = mcd(546,105) = mcd(441,105) = mcd(336,105) = mcd(231,105) = mcd(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21

Por supuesto, este algoritmo es susceptible de ciertas mejoras. Por ejemplo, multiplicar y dividir por 2 es algo sencillo utilizando las operaciones de bits: al desplazar un bit a la izquierda estamos multiplicando por 2 y al desplazarlo a la derecha estamos dividiendo por 2. De esta forma, podríamos ahorrarnos algunos pasos en el ejemplo anterior:

function mcd_mejorado(x, y) {
var mayor = max(x,y);
var menor = min(x,y);
if (mayor > (menor << 1)) {
return mcd_mejorado(mayor - (menor << 1), menor);
} else {
return mcd(mayor,menor); //llamada a la funcion anterior
}
}

Volviendo a nuestro ejemplo:

mcd_mejorado(1617,756) = mcd_mejorado(756,105) = mcd_mejorado(546,105) = mcd_mejorado(336,105) = mcd_mejorado(126,105) = mcd(21,105) = mcd(21,84) = mcd(21,63) = mcd(21,42) = mcd(21,21) = 21