Даны два числа. Найти их наибольший общий делитель.
В данной задаче требуется реализовать алгоритм Евклида. Все решения данной задачи будут просматриваться и обнуляться те из них, которые будут реализовывать простой перебор делителей.
Вводятся два натуральных числа, не превышающих 109.
Выведите НОД введенных чисел.
| Пример ввода | Пример вывода |
9 12 |
3 |