Продвинутый способ найти наибольший общий множитель из двух целых чисел называется алгоритм Евклида. Он часто используется в программировании.
Алгоритм Евклида нахождения НОД
Для нахождения НОД методом Евклида онлайн — перейдите по ссылке
Нахождение НОД при помощи алгоритма Евклида происходит в три этапа:
• разделите большее число на меньшее. Запишите остаток.• поделить меньшее число на остаток от первого действия и снова записать остаток.
• повторять до тех пор, пока остаток не станет равным нулю .
Последний ненулевой остаток — это наибольший общий множитель.
Пример работы алгоритма Евклида
Пример: Найти наибольший общий делитель чисел 112 и 42.
— делим 112 на 42. 112 : 42 = 2 ( остаток 28 ) — Получили 2 с остатком 28.
— делим 42 на 28. 42 : 28 = 1 ( остаток 14 ) — Получаем 1 с остатком 14.
— делим 28 на 14. 28 : 14 = 2 ( остаток 0) — Получаем 2 с остатком 0.
Получили остаток 0, значит алгоритм закончен.
Последний ненулевой остаток равен 14, поэтому наибольший общий делитель чисел 112 и 42 равен 14 . Можно записать ответ: НОД ( 112, 42 ) = 14.