✏️ Как вычислить наибольший общий делитель (НОД) в Питоне?

Как вычислить НОД в Python

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

1. Реализация алгоритма Евклида

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

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

Чтобы вычислить НОД двух чисел, просто вызовите эту функцию, передав исходные числа в качестве аргументов:

num1 = 12
num2 = 8
result = gcd_euclidean(num1, num2)
print("НОД чисел", num1, "и", num2, "равен", result)
    

В консоли вы увидите такой результат:

НОД чисел 12 и 8 равен 4
    

2. Использование функции math.gcd

Python также предоставляет встроенную функцию math.gcd, которая может использоваться для вычисления НОД:

import math

num1 = 18
num2 = 9
result = math.gcd(num1, num2)
print("НОД чисел", num1, "и", num2, "равен", result)
    

В результате выполнения кода вы получите:

НОД чисел 18 и 9 равен 9
    

3. Рекурсивный подход

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

def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)
    

Теперь можно вызвать функцию и передать исходные числа:

num1 = 24
num2 = 12
result = gcd_recursive(num1, num2)
print("НОД чисел", num1, "и", num2, "равен", result)
    

Вы получите следующий результат:

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

Заключение

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