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

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

Существует несколько способов реализации функции gcd в Python.

Способ 1. Используем стандартную библиотеку Python. Для этого нужно импортировать математический модуль и вызвать функцию gcd:

import math
a = 12
b = 18
# Находим наибольший общий делитель с помощью функции из стандартной библиотеки
res = math.gcd(a, b)
print(res) # Результат: 6

Способ 2. Реализуем функцию gcd самостоятельно. Для этого можем использовать алгоритм Евклида:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
# Используем функцию gcd
a = 12
b = 18
res = gcd(a, b)
print(res) # Результат: 6

В этом примере мы используем цикл while, который продолжает работать, пока b не станет равным 0. Внутри цикла мы меняем значения a и b местами, а затем "обрезаем" одно из чисел на его модуль по модулю от второго числа. Таким образом, мы получаем новые значения a и b и продолжаем цикл до тех пор, пока b не станет равным 0. В конечном итоге мы получаем a, которое и является искомым наибольшим общим делителем.

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