Máximo común divisor (GCD)
Dado un par de números enteros positivos a y b, se pide calcular el máximo común divisor de ambos. El máximo común divisor es aquel número que divide tanto a a como a b y que es el mayor de todos los posibles divisores comunes.
Ten en cuenta que el máximo común divisor de cualquier número y 0 es el propio número.
Entrada
La única línea de la entrada contiene dos números 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 |
0 13 | 13 |
Explicación
8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ el mayor divisor común es 4
54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ el mayor divisor común es 6
17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ el mayor divisor común es 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB