Máximo Divisor Comum (GCD)
Dadas duas inteiros positivos
a e b, pretende-se calcular o máximo divisor comum (MDC) entre eles. O MDC é o número que divide tanto a como b e é o maior de todos os divisores possíveis.Note que o máximo divisor comum de qualquer número e 0 é o próprio número.
Entrada
A única linha da entrada contém dois inteiros
a e b (0 ≤ a, b ≤ ).Saída
O programa deve imprimir o máximo divisor comum de
a e b.Exemplos
Entrada | Saída |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
Explicação
- 8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ o maior divisor comum é 4
- 54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ o maior divisor comum é 6
- 17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ o maior divisor comum é 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB