Найди наибольший общий делитель натуральных чисел X и у Если

Предыдущий
вопрос Следующий
вопрос

вы хотите найти наибольший общий делитель натуральных чисел X и Y, можно воспользоваться алгоритмом поиска наибольшего общего делителя (НОД) с помощью алгоритма Евклида.

Алгоритм Евклида работает следующим образом:

Если X равен 0, то НОД(X,Y) = YЕсли Y равен 0, то НОД(X,Y) = XИначе, повторно применяем алгоритм Евклида к паре чисел (Y, X mod Y), где mod обозначает операцию взятия остатка от деления.

Продолжаем повторять шаг 3, пока одно из чисел не станет равным 0. Полученное число будет являться НОД(X,Y).

Пример:
Пусть X = 24, Y = 36.
24 mod 36 = 24
36 mod 24 = 12
24 mod 12 = 0

НОД(24,36) = 12

Таким образом, наибольший общий делитель чисел X и Y равен 12.