Python GCD: Нахождение наибольшего общего делителя

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

Для реализации данного алгоритма в языке программирования Python необходимо написать соответствующую функцию. Вот пример такой функции:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Обратите внимание, что переменные a и b включают в себя числа, для которых мы хотим найти НОД. Основная логика алгоритма заключается в выполнении итераций, пока b не станет равным нулю. В каждой итерации значения переменных a и b обновляются в соответствии с алгоритмом Евклида.

Ниже приведены несколько примеров использования данной функции:

print(gcd(24, 36))  # Ожидаемый результат: 12
print(gcd(60, 48))  # Ожидаемый результат: 12
print(gcd(17, 23))  # Ожидаемый результат: 1

В первом примере gcd(24, 36) функция вернет 12, так как НОД для этих двух чисел равен 12. Аналогично во втором примере gcd(60, 48) результатом будет 12.

Наконец, в третьем примере gcd(17, 23) результатом будет 1, поскольку эти два числа являются взаимно простыми и их НОД равен 1.

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