Алгоритм Евклида. Нахождение НОД

Алгоритм Евклида — это один из старейших численных алгоритмов для нахождения наибольшего общего делителя двух целых чисел. Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые его описал.

def nod(x, y):
    while (x != y):
        if x > y:
            x = x - y
        else:
            y = y - x
    return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 1. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием меньшего числа из большего числа.

Введите первое число: 30855
Введите второе число: 41514
Наибольший общий делитель 561

Скр. 1. Результат работы программы нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y):
    while (x != y):
        x, y = abs(x - y), min(x, y)
    return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 2. Функция нахождения наибольшего общего делителя двух целых чисел с вычитанием меньшего числа из большего числа.

В программе листинг 2 используются функции abs() и min() вместо операторов if и else в программе листинг 1.

def nod(x, y):
    while (x % y !=0 and y % x !=0):
        if x > y:
            x = x % y
        else:
            y = y % x
    return min(x, y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 3. Функция нахождения наибольшего общего делителя двух целых чисел с нахождением остатка от деления большего числа на меньшее.

def nod(x, y):
    while (x % y !=0 and y % x !=0):
        x, y = max(x, y) % min (x, y), min(x, y)
    return min(x, y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 4. Функция нахождения наибольшего общего делителя двух целых чисел с нахождением остатка от деления большего числа на меньшее.

В программе листинг 4 используются функции max() и min() вместо операторов if и else в программе листинг 3.

def nod(x, y):
    if (y != 0):
        return nod(min(x, y), max(x, y) % min (x, y))
    else:
        return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 5. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел.

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

Пусть Y = X⋅Q + R, тогда НОД (X, Y) = НОД (X, R), где Q целая часть, а R дробная часть от деления Y/X.
НОД(R, 0) = R для любого ненулевого R (так как 0 делится на любое целое число).

def nod(x, y):
    while y != 0:
        x, y = y, x % y
    return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 6. Функция нахождения наибольшего общего делителя двух целых чисел без рекурсии.

Функция нахождения наибольшего общего делителя двух целых чисел без рекурсии в программе листинг 6 написана исходя из тех же двух утверждений что и программа листинг 5.

Следует заметить, что в программе листинг 6, так же как и в остальных выше приведённых программах с нахождением остатка от деления большего числа на меньшее используется нахождение остатка от деления большего числа на меньшее. Но в отличие от других приведённых выше программ, выбор большего и меньшего значения аргументов x и y в программе листинг 6 осуществляется за счёт лишней итерации цикла while, вместо использования функций min() и max(). Кроме того, эта лишняя итерация цикла while в программе листинг 6 происходит только в том случае, когда x оказывается меньше y. А это случается только один раз, когда аргументы функции следуют в порядке, с начала меньший, а затем больший.

Сказанное справедливо и для рекурсивной функции нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y):
    if (y != 0):
        return nod(y, x % y)
    else:
        return x

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 7. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел.

def nod(x, y):
    return x if (y == 0) else nod(y, x % y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 8. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел с использованием тернарного оператора Python.

def nod(x, y): return x if (y == 0) else nod(y, x % y)

x = int(input('Введите первое число: '))
y = int(input('Введите второе число: '))
print('Наибольший общий делитель', nod(x, y))

Лист. 8-2. Рекурсивная функция нахождения наибольшего общего делителя двух целых чисел одной строкой.

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

Python