Máximo común divisor en C - Algoritmo de Euclides

Resumen: aplicar el algoritmo de Euclides en el lenguaje C para obtener el máximo común divisor (MCD) de dos números; implementando dos funciones:

• Una utiliza el ciclo while
• Otra, que utiliza la recursión o recursividad

Máximo común divisor en C

Si no sabes lo que es este término, mira la Wikipedia. El algoritmo es realmente sencillo y puede ser implementado en pocas líneas de código.

Con ciclo while

Con este ciclo simplemente operamos mientras que b sea distinto de 0.

Dentro del ciclo, guardamos el valor de b en una variable temporal, después asignamos a b el valor de a % b que es sacar el residuo de dividir de manera entera a entre b.

int maximo_comun_divisor(int a, int b) {
    int temporal;//Para no perder b
    while (b != 0) {
        temporal = b;
        b = a % b;
        a = temporal;
    }
    return a;
}

Finalmente, a tomará el valor de temporal, que era el que inicialmente tenía b. En algún momento b es 0 y se termina el ciclo, que es en donde regresamos a, el cuál tendrá el último valor de b antes de haber obtenido el residuo.

Usando recursión

Como la definición dice que mcd(a,b) es lo mismo que mcd(b, a % b) podemos aplicar recursión o recursividad para llamar a la misma función dentro de sí misma, quedando así:

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

La condición de salida es que b sea 0, lo cual pasará en algún momento pues en algún momento el residuo de a / b será 0.

Poniendo todo junto

El código completo junto con una demostración de su uso queda así:

/**
 * Máximo común divisor en C con el algoritmo de Euclides
 * implementado con ciclo while y con recursión / recursividad
 * @date 2019-12-18
 * @author parzibyte
 * https://parzibyte.me/blog/
*/
 * */
#include <stdio.h>

int maximo_comun_divisor(int a, int b) {
    int temporal;//Para no perder b
    while (b != 0) {
        temporal = b;
        b = a % b;
        a = temporal;
    }
    return a;
}

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

int main(void) {
    printf("MCD de 50 y 120: %d\n", maximo_comun_divisor(50, 120));
    printf("MCD de 50 y 120 (recursivo): %d\n", maximo_comun_divisor_recursivo(50, 120));
    printf("MCD de 7 y 5: %d\n", maximo_comun_divisor(7, 5));
    printf("MCD de 7 y 5 (recursivo): %d\n", maximo_comun_divisor_recursivo(7, 5));
    return 0;
}

Como se puede ver, ambos métodos funcionan para obtener el máximo común divisor en C, tanto el recursivo como el iterativo.

Notas sobre el máximo común divisor en C

Recuerda que podrías almacenar el resultado en una variable. Por ejemplo:

int mcd = maximo_comun_divisor(50, 120);

También se pueden enviar variables:

int a = 50, b = 120; int mcd = maximo_comun_divisor(a, b);

Por otro lado, tanto a y b pueden ser proporcionadas por el usuario, y leídas por el programa usando scanf.

Conclusión

Te animo a leer más sobre C en mi blog.