Делители числа и алгоритм Евклида
💻 Информатика · 9 класс
Делители и наибольший общий делитель
Делитель числа — это число, на которое оно делится без остатка. Например, делители числа 12 — это 1, 2, 3, 4, 6 и 12. Наибольший общий делитель (НОД) двух чисел — это самое большое число, на которое делятся оба. Поиск НОД — классическая задача программы 9 класса, и решают её несколькими способами.
Перебор делителей
Чтобы найти все делители числа n, перебирают числа от 1 до n и проверяют делимость условием n mod d = 0. Так же находят количество делителей или их сумму. Этот приём используют и при проверке числа на простоту: у простого числа ровно два делителя.
НОД перебором
Простой способ найти НОД двух чисел — перебрать возможных кандидатов от меньшего из чисел вниз до единицы и взять первое число, которое делит оба нацело. Способ понятный и наглядный, но при больших числах работает медленно, потому что приходится проверять много вариантов.
Алгоритм Евклида
Алгоритм Евклида — быстрый и древний способ найти НОД. Он основан на правиле: НОД двух чисел не меняется, если большее число заменить остатком от деления большего на меньшее. Процесс повторяют, пока одно из чисел не станет нулём; тогда второе число и есть искомый НОД.
пока b ≠ 0:
r = a mod b
a = b
b = r
ответ = a
Проследим работу алгоритма для чисел 48 и 36 по таблице:
a | b | a mod b |
|---|---|---|
| 48 | 36 | 12 |
| 36 | 12 | 0 |
| 12 | 0 | — |
Когда b стало равным нулю, ответом стало число 12 — это и есть НОД чисел 48 и 36. Алгоритм сделал всего два шага, тогда как перебор делителей потребовал бы куда больше проверок. В этом и состоит преимущество способа Евклида.
Существует и более старый вариант алгоритма — через вычитание: из большего числа вычитают меньшее, пока числа не станут равны. Этот вариант работает, но медленнее, чем версия через остаток.
Связь НОД и НОК
С наибольшим общим делителем тесно связано наименьшее общее кратное (НОК) — наименьшее число, которое делится на оба заданных. Эти величины связаны простой формулой:
НОК(a, b) = a * b / НОД(a, b)
Поэтому, найдя НОД алгоритмом Евклида, легко вычислить и НОК. Например, для чисел 48 и 36: НОД равен 12, значит НОК равен 48 * 36 / 12 = 144. Это часто требуется при работе с дробями и в текстовых задачах.
Частые ошибки. В алгоритме Евклида нужно обязательно сохранять остаток во временной переменной r перед тем, как менять значения a и b, иначе данные потеряются и ответ будет неверным. Также следите за условием выхода: цикл продолжается, пока b не равно нулю, а ответом служит именно a, а не b.Кратко о главном
- Делитель — число, на которое делится нацело; их находят перебором с условием
n mod d = 0. - НОД — наибольшее число, делящее оба заданных числа.
- Алгоритм Евклида заменяет большее число остатком и работает, пока второе не станет нулём.
- Ответом в алгоритме служит то число, что осталось ненулевым.
- Алгоритм Евклида намного быстрее простого перебора делителей.