GCD)

В этом примере посмотрим, как найти наибольший общий делитель (НОД, в английской традиции — HCF или GCD) двух чисел на Python. Покажем два способа: простой перебор и более быстрый алгоритм Евклида.

Что нужно знать

Перед изучением примера полезно понимать:

Функции в Python — функции
Рекурсия в Python — рекурсия
Аргументы функций в Python — аргументы функции
Оператор if…else в Python — условный оператор if...else

Примечание

Наибольший общий делитель двух чисел — это наибольшее целое положительное число, на которое оба числа делятся без остатка. Например, НОД 12 и 14 равен 2.

Пример 1. Через цикл

# Python program to find H.C.F of two numbers

# define a function
def compute_hcf(x, y):

# choose the smaller number
    if x > y:
        smaller = y
    else:
        smaller = x
    for i in range(1, smaller+1):
        if((x % i == 0) and (y % i == 0)):
            hcf = i
    return hcf

num1 = 54
num2 = 24

print("The H.C.F. is", compute_hcf(num1, num2))

Вывод

The H.C.F. is 6

Два целых числа num1 и num2 передаются в функцию compute_hcf(). Внутри функция находит их НОД и возвращает его.

Сначала определяем меньшее из двух чисел: общий делитель не может быть больше любого из них. Затем циклом for пробегаем все числа от 1 до этого меньшего значения включительно.

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

Совет

Такой способ простой и наглядный, но медленный. Для больших чисел лучше использовать алгоритм Евклида — он намного быстрее.

Алгоритм Евклида

Алгоритм основан на том, что НОД двух чисел равен НОДу их разности и меньшего из них.

На практике это делается так: большее число делится на меньшее, берётся остаток. Затем меньшее число делится на этот остаток. И так пока остаток не станет равен нулю.

Пример: ищем НОД для 54 и 24. Делим 54 на 24 — остаток 6. Делим 24 на 6 — остаток 0. Значит, НОД равен 6.

Пример 2. Алгоритм Евклида

# Function to find HCF the Using Euclidian algorithm
def compute_hcf(x, y):
   while(y):
       x, y = y, x % y
   return x

hcf = compute_hcf(300, 400)
print("The HCF is", hcf)

Цикл крутится, пока y не станет равно нулю. Выражение x, y = y, x % y — это короткая запись для одновременного обмена и пересчёта значений: x получает старый y, а y — остаток от деления x на y.

Как только y обнуляется, искомый НОД оказывается в x.