Алгоритм Евклида на Питоне: подробное описание и примеры

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

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

return

b

a

Эта функция рекурсивно вызывает себя с помощью оператора

return

b

a

Например, если мы вызовем эту функцию с аргументами 24 и 36, то получим:

>>> gcd(24, 36)
12

Это означает, что наибольший общий делитель чисел 24 и 36 равен 12.

gcd

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

gcd

Например, мы можем использовать эту функцию для нахождения числа, которое не имеет общих делителей с заданным числом:

def coprime(n):
    for i in range(2, n):
        if gcd(n, i) == 1:
            return i
    return None

n

n

gcd

None

Эта функция находит первое число от 2 до

n

n

gcd

None

Например, если мы вызовем эту функцию с аргументом 10, то получим:

>>> coprime(10)
3

Это означает, что первое число от 2 до 10, которое не имеет общих делителей с 10, равно 3.