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.

See the gist on github.

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í:

See the gist on github.

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í:

See the gist on github.

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.