Intermedio · algoritmo de Euclides
MCD (Máximo común divisor)
mcd(12, 18) = 6. Euclides: mcd(a, b) = mcd(b, a mod b) hasta que b sea cero. El algoritmo más antiguo aún en uso diario.
Problema
Entrada: una línea con dos enteros a b (0 ≤ a, b ≤ 10⁹, no ambos cero).
Salida: su máximo común divisor.
Ejemplo:
| Entrada | Salida |
|---|---|
12 18 | 6 |
17 5 | 1 |
Tu solución
Entrada personalizada para "Probar mi entrada"
La corrección se ejecuta por completo en tu navegador contra pruebas ocultas. Tu código se guarda localmente mientras escribes. Ctrl+Enter corrige.
¿Atascado? Pistas
Pista 1 — el algoritmo completo
while (b != 0) { int t = b; b = a % b; a = t; } — cuando termina, a es la respuesta. Tres líneas, sin recursión.
Pista 2 — por qué funciona
Cualquier número que divida tanto a a como a b también divide a a mod b — así que (a, b) y (b, a mod b) comparten TODOS los divisores comunes. El segundo número se encoge rápido: al menos se reduce a la mitad cada dos rondas.
Solución (¡inténtalo primero!)
string[] partes = Console.ReadLine().Split(' ');
int a = int.Parse(partes[0]);
int b = int.Parse(partes[1]);
while (b != 0) { int t = b; b = a % b; a = t; }
Console.WriteLine(a);Euclides es la puerta a la teoría de números — el MCM queda a una línea: a / mcd * b. Siguiente: Comprobar primo.