Алгоритмы на Python

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

В этом уроке вы найдёте наибольший общий делитель (НОД) двух чисел с помощью алгоритма Евклида.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

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

Пример из жизни

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

От вырезания квадратов к коду
first, second▭ Прямоугольник: 48 × 18
first % second✂️ Остаток после вырезания квадратов по меньшей стороне
first, second = second, first % second🔁 Повторить с оставшимся куском
while second:✅ Ничего не осталось: сторона - это НОД, 6
gcd(a, b) = gcd(b, a % b), пока остаток не станет 0.
Одним предложением

Наибольший общий делитель (НОД) двух целых чисел - наибольшее положительное целое число, на которое делятся оба. Алгоритм Евклида находит его, заменяя пару (a, b) на (b, a % b), пока b не станет 0.

Главное

  1. first, second = second, first % second заменяет пару меньшим числом и остатком.
  2. Для 48 и 18 пары такие: (48, 18), (18, 12), (12, 6), (6, 0).
  3. while second: останавливается, когда остаток становится 0.
  4. return abs(first) даёт положительный результат даже для отрицательных входных данных.

Когда это нужно?

  • Сокращение дробей и отношений.
  • Поиск наименьшего общего кратного: a * b // gcd(a, b).
  • Числовые головоломки, модульная арифметика и основы криптографии.

Когда это не нужно

  • Настоящий код: встроенный math.gcd в последних версиях Python принимает любое число аргументов.
  • Поиск всех общих делителей: НОД даёт только наибольший.

Пример кода

Запустить код →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Получить кнопку запуска для этого примера

Результат выполнения

6

Разбор кода

На каждом шаге пара (first, second) заменяется на (second, first % second). Когда остаток становится равен 0, значение в first и есть НОД, поэтому НОД 48 и 18 равен 6. Функция abs() гарантирует, что результат всегда положительный. Число шагов растёт очень медленно с ростом чисел, примерно как O(log n).

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

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

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Вычитание вместо остатка

Многократное вычитание даёт тот же ответ, но работает очень медленно, если числа сильно различаются.

Ошибка
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
Исправление
while second:
    first, second = second, first % second

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи