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.
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í:
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í:
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
Si quieres probar el ejercicio en línea haz click aquí.
Te animo a leer más sobre C en mi blog.
