Наибольший общий делитель (НОД) двух целых чисел

Этот калькулятор находит наибольший общий делитель (НОД) двух целых чисел алгоритмом Евклида.

PLANETCALC, Наибольший общий делитель (НОД) двух целых чисел

Наибольший общий делитель (НОД) двух целых чисел

НОД
 

Алгоритм Евклида для нахождения НОД

Сейчас я расскажу вам, как находить наибольший общий делитель двух целых чисел алгоритмом Евклида.

Это довольно просто. Надо строить уменьшающуюся последовательность чисел, первое число которой это максимальное из двух целых, чей НОД мы ищем, второе — соответственно, минимальное из двух целых, а каждое следующее представляет из себя остаток от деления пред-предыдущего на предыдущее. Последний ненулевой член последовательности и есть НОД.

Чтобы было легче воспринять, проиллюстрируем это примером. Найдем НОД для чисел 13 и 17.

1 шаг. Сформируем два первых числа последовательности
17, 13

2 шаг. Третье число последовательности — остаток от деления 17 на 13, то есть 4
17, 13, 4

3 шаг. Четвертое число последовательности — остаток от деления 13 на 4, то есть 1
17, 13, 4, 1

4 шаг. Пятое число последовательности — остаток от деления 4 на 1, то есть 0
17, 13, 4, 1, 0

Перед нулем стоит 1 — последний ненулевой член последовательности. Следовательно, это и есть искомый НОД. С учетом того, что и 13 и 17 — простые числа, это действительно так.

Ссылка скопирована в буфер обмена
PLANETCALC, Наибольший общий делитель (НОД) двух целых чисел

Комментарии