Lenguaje de programación C

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

Máximo común divisor en C con algoritmo de Euclides – Ejecución del programa

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
 * @see 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.

Estoy aquí para ayudarte 🤝💻


Estoy aquí para ayudarte en todo lo que necesites. Si requieres alguna modificación en lo presentado en este post, deseas asistencia con tu tarea, proyecto o precisas desarrollar un software a medida, no dudes en contactarme. Estoy comprometido a brindarte el apoyo necesario para que logres tus objetivos. Mi correo es parzibyte(arroba)gmail.com, estoy como@parzibyte en Telegram o en mi página de contacto

No te pierdas ninguno de mis posts 🚀🔔

Suscríbete a mi canal de Telegram para recibir una notificación cuando escriba un nuevo tutorial de programación.
parzibyte

Programador freelancer listo para trabajar contigo. Aplicaciones web, móviles y de escritorio. PHP, Java, Go, Python, JavaScript, Kotlin y más :) https://parzibyte.me/blog/software-creado-por-parzibyte/

Entradas recientes

Servidor HTTP en Android con Flutter

El día de hoy te mostraré cómo crear un servidor HTTP (servidor web) en Android…

4 días hace

Imprimir automáticamente todos los PDF de una carpeta

En este post te voy a enseñar a designar una carpeta para imprimir todos los…

5 días hace

Guía para imprimir en plugin versión 1 desde Android

En este artículo te voy a enseñar la guía para imprimir en una impresora térmica…

1 semana hace

Añadir tasa de cambio en sistema de información

Hoy te voy a mostrar un ejemplo de programación para agregar un módulo de tasa…

2 semanas hace

Comprobar validez de licencia de plugin ESC POS

Los usuarios del plugin para impresoras térmicas pueden contratar licencias, y en ocasiones me han…

2 semanas hace

Imprimir euro € en impresora térmica

Hoy voy a enseñarte cómo imprimir el € en una impresora térmica. Vamos a ver…

4 semanas hace

Esta web usa cookies.