Задача "НОД - алгоритм Евклида"

Даны два числа. Найти их наибольший общий делитель.

В данной задаче требуется реализовать алгоритм Евклида. Все решения данной задачи будут просматриваться и обнуляться те из них, которые будут реализовывать простой перебор делителей.

Вводятся два натуральных числа, не превышающих 109.

Выведите НОД введенных чисел.

Пример вводаПример вывода
9 12
3