Наибольший общий делитель (GCD)
Пусть даны два положительных целых числа
a и b. Необходимо найти их наибольший общий делитель (GCD). Наибольший общий делитель — это число, которое без остатка делит и a, и b, причём из всех возможных делителей оно является наибольшим.Обратите внимание, что если одно из чисел равно 0, то наибольший общий делитель равен другому числу.
Входные данные
В единственной строке ввода содержится два целых числа
a и b (0 ≤ a, b ≤ ).Выходные данные
Программа должна вывести наибольший общий делитель чисел
a и b.Примеры
Входные данные | Выходные данные |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
Пояснение
- 8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ наибольший общий делитель равен 4
- 54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ наибольший общий делитель равен 6
- 17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ наибольший общий делитель равен 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB