Как посчитать НОД в Python: простой метод и алгоритм Евклида

НОД, или наибольший общий делитель, двух чисел можно посчитать с помощью алгоритма Эвклида.

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

num1 = 24
num2 = 36
result = gcd(num1, num2)
print(f"НОД {num1} и {num2} равен {result}")

В этом примере мы определяем функцию gcd (наибольший общий делитель) с помощью алгоритма Эвклида. Затем мы вызываем функцию с двумя числами 24 и 36 и выводим результат. В данном случае, НОД 24 и 36 равен 12.

Как посчитать НОД в Python

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

Метод 1: Использование алгоритма Евклида

Алгоритм Евклида - это один из самых распространенных способов поиска НОД. Он основан на следующей формуле: если а больше b, то НОД(a, b) равен НОД(a % b, b). Если b больше a, то НОД(a, b) равен НОД(a, b % a). Вот пример кода на Python, который реализует алгоритм Евклида:

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

    num1 = 24
    num2 = 36
    result = gcd(num1, num2)
    print(f"НОД чисел {num1} и {num2} равен {result}")
    

Вывод программы будет следующим:

НОД чисел 24 и 36 равен 12

Метод 2: Использование встроенной функции math.gcd()

Python также предоставляет встроенную функцию math.gcd(), которая позволяет нам легко найти НОД двух чисел. Здесь не нужно самостоятельно реализовывать алгоритм Евклида, так как он уже встроен в эту функцию. Вот пример кода на Python, который использует math.gcd():

    import math

    num1 = 24
    num2 = 36
    result = math.gcd(num1, num2)
    print(f"НОД чисел {num1} и {num2} равен {result}")
    

Вывод программы будет таким же:

НОД чисел 24 и 36 равен 12

Итог

В этой статье мы рассмотрели два способа нахождения НОД в Python. Первый метод основан на алгоритме Евклида, который реализован вручную с использованием цикла while. Второй метод использует встроенную функцию math.gcd(), которая уже включает в себя алгоритм Евклида. Вы можете выбрать любой из этих методов в зависимости от вашего предпочтения и потребностей проекта. Оба метода дадут вам правильный результат, но встроенная функция math.gcd() предлагает более простое и компактное решение.