GCD (MCD) – Algoritmo de Euclides
Después de ejecutar varias iteraciones de este algoritmo, empezamos a notar que se repiten ciertas operaciones y que, en realidad, podemos optimizar la búsqueda del máximo común divisor.
Cuando utilizamos la resta, vamos restando el número más pequeño del más grande hasta obtener un resultado de 0 o un número que coincida con el MCD. Podemos acelerar el proceso usando el resto de la división (operación módulo) entre el número más grande y el más pequeño. Con la operación módulo, dividimos repetidamente el número más grande por el más pequeño y nos quedamos con el resto hasta que ese resto sea 0. El último resto distinto de 0 es el MCD.
Puedes pensar en la operación módulo como una manera más eficaz de encontrar el MCD. En lugar de restar varias veces el número más pequeño al más grande, utilizas la división para reducir rápidamente el número más grande. Esto implica que estás dividiendo ambos números por sus divisores en común y, de esta forma, llegas al máximo común divisor mucho más rápido.
a, b = int(input()), int(input())
while a > 0 and b > 0: # En caso de que a o b sea 0 => el otro es el GCD
a, b = b, a % b # El gcd de (a, b) es igual al gcd de (b, a % b)
d = b if a == 0 else a # Si a es 0 => b es el GCD, si b es 0 => a es el GCD
print('gcd:', d)Este algoritmo se mencionó por primera vez en un libro de Euclides escrito alrededor del año 300 a. C.
Veamos algunas simulaciones del algoritmo:
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ GCD = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ GCD = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ GCD = 1
Entrada
La única línea de la entrada contiene dos enteros
a y b (0 ≤ a, b ≤ ).Salida
El programa debe imprimir el máximo común divisor de
a y b.Ejemplos
Input | Output |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB