Высший общий коэффициент Python (HCF/GCD)

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

Обзор

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

Алгоритм Евклида — чрезвычайно эффективный метод вычисления HCF. В нем говорится, что НОД двух чисел также делит их разницу.

В Python мы реализуем это итеративно, используя цикл while, в котором мы постоянно заменяем большее число остатком от его деления.

Код и вывод выполнения

Реализация евклидова цикла для поиска HCF/GCD двух чисел.

hcf_gcd.py

Попробуйте в редакторе

def find_gcd(a, b):
    # Euclidean Algorithm
    while b != 0:
        a, b = b, a % b
    return a

print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))

Терминальный выход

GCD of 36 and 60 is: 12
GCD of 17 and 5 is:  1

Пошаговая реализация

Упрощение дробей и математические движки
Алгоритмы криптографии (например, генерация закрытых ключей RSA)
Составление расписания периодических мероприятий

Часто задаваемые вопросы

Есть ли в Python встроенная функция GCD?

Да! Стандартная библиотека Python содержит `math.gcd(a, b)`, который использует скомпилированную реализацию C под капотом.

Связанные темы

Наименьшее общее кратное Python (LCM)

Найдите наименьшее общее кратное (LCM) двух чисел, используя их отношение HCF в Python.

Скрипт простого калькулятора Python

Создайте базовый калькулятор на Python. Узнайте, как сопоставлять математические операторы, использовать потоки выполнения пользователей и обрабатывать логику собственными средствами.