Tiempo: O(log n)
Espacio: O(1)

Es un algoritmo para el cálculo en tiempo logarítmico del MCD de dos números. Se basa en lo siguiente:

Dado A y B enteros, y A > B:
MCD (A, B) = MCD (A, r)
Donde r es el residuo de A entre B (A mod B)

Demostración

Queremos demostrar: ¿ MCD (A, B) = MCD (B, r) ?

La demostración a continuación demostrará primero que:

MCD (A, B) | MCD (B, r)

Luego que:

MCD (B, r) | MCD (A, B)

Una vez demostrado eso, podemos afirmar que:

MCD (A, B) = MCD (B, r)

Ya que siempre se cumple:
Si X|Y y Y|X entonces X = Y

i). ¿ MCD (A, B) | MCD (B, r) ?

Llamemos d al MCD (A, B):

MCD (A, B) = d, esto significa:
d|A y d|B

Ahora sabemos que r = A mod B
lo cual es lo mismo que decir:

r = A – B * q

Si d|B es obvio que d|(B*q)

d|A y d|(B*q), entonces:
d| (A – B*q) =
d| (r)

Dado que d|B y d|r entonces, d|MCD(B, r)

Nota: Colocamos d|MCD(B, r) ya que d puede ser el MCD(B, r) o ser un divisor común no máximo entre B y r, el cual por ser divisor de B y r por obvias razones es múltiplo de MCD(B, r)

Reemplazando d tenemos:

MCD (A, B) | MCD (B, r)

ii). ¿ MCD (B, r) | MCD (A, B) ?

Llamemos d’ al MCD (B, r):

MCD (B, r) = d’, esto significa:
d’|B y d’|r

r = A – B*q, entonces:

d’|A

dado que d’|A y d’|B, entonces: d’|MCD(A, B) y reemplazando el valor de d’:

MCD (B, r)|MCD (A, B)

Una vez demostrado i) y ii) podemos afirmar:

MCD (A, B) = MCD (B, r)

Lo demostrado anteriormente nos permite reducir el cálculo del MCD de dos números grandes al de dos números más pequeños, por ejemplo:

El algoritmo consiste en reemplazar el mayor número con el residuo de dividir el mayor entre el menor, y seguir de forma iterativa o recursiva hasta que el menor de los números sea 0, en dicho caso se retorna el mayor el cual será el MCD y por lo tanto nuestra respuesta

MCD (162, 48)  = 
MCD (48, 18)  = 
MCD (18, 12) = 
MCD (12, 6) = 
MCD (6, 0) = 
6

Implementaciones en C++

Implementación iterativa:

int mcd (int a, int b) {
    int temp;
    while(b!=0) {
        temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

Implementación recursiva:

int mcd (int a, int b) {
    if (b == 0) return a
    return mcd (b, a%b)
}

Para más de dos números:

int mcd (int a, int b); /* implementación (recursiva 
                         * o iterativa) se muestra 
                         * arriba */
#define N 4
int _mcd(int arr[N]) {
    int d = mcd (arr[0], arr[1]);
    for (int i=2; i<N; i++) 
        d = mcd (d, arr[i]);
    return d;
}

Para más de dos números con templates:

int mcd (int a, int b); /* implementación (recursiva 
                         * o iterativa) se muestra 
                         * arriba */
template<int N_VALS>
int __mcd(int arr[N_VALS]) {
    int d = mcd (arr[0], arr[1]);
    for (int i=2; i<N_VALS; i++) 
        d = mcd (d, arr[i]);
    return d;
}

Probando las funciones:

int main() {

    cout<<"test f. mcd\n";
    cout<<mcd (0, 4)<<endl;
    cout<<mcd (9, 12)<<endl;
    cout<<mcd (1234, 14123)<<endl;
    cout<<mcd (1, 100)<<endl;

    cout<<"test f. _mcd\n";
    int arr[4] {2*2*3, 2*5*7, 2*3*3*5, 2*2*2*13};
    cout<<_mcd(arr)<<endl;

    cout<<"test f. __mcd\n";
    int arr2[5] {3*2*3, 3*5*7, 3*3*3*5, 3*2*2*13, 3*17};
    cout<<__mcd<5>(arr2);
}

OUTPUT
test f. mcd
4
3
1
1
test f. _mcd
2
test f. __mcd
3