Алгоритм нахождения наибольшего общего делителя

Наибольший общий делитель (НОД, Greatest Common Divisor) – это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

НОД пары целых чисел можно найти с помощью алгоритма Евклида:

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД и работа алгоритма завершается.
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 1.

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

1. Из большего числа вычитаем меньшее.
2. Если получается 0, то числа равны друг другу и являются НОД. Работа алгоритма завершается.
3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
4. Переходим к пункту 1.

Реализация алгоритма Евклида "в лоб":

while a and b:
    if a > b:
        a = a % b
    else:
        b = b % a
print a + b

Предполагается, что НОД вычисляется для положительных целых чисел. Заключительный print выводит НОД, которым является a или b (переменная, значение которой не равно НОД, при этом равняется нулю).

Немного подумав, код можно немного сократить:

if a < b:
    b, a = a, b
while b:
    a, b = b, a % b
print a

Можно сделать код еще короче:

while b:
    a, b = b, a % b
print a

Однако, если a < b, то алгоритм делает лишний шаг (обмен значений a и b). Нужна ли такая оптимизация кода — решайте сами.

Рекурсивный вариант вычисления НОД:

def gcd(u, v):
    return gcd(v, u % v) if v else abs(u)

"Лобовая" реализация алгоритма Никомаха:

while a - b:
    if a > b:
        a = a - b
    else:
        b = b - a
print a

Улучшенный код:

while a - b:
    a, b = b, abs(a - b)
print a

Если интересно посмотреть на то, как идет процесс поиска НОД, можно поместить в цикле print и перенаправить вывод в файл, допустим gcd.txt. Тогда, поиграв немного со столбчатыми диаграммами в matplotlib (текст программы), получим такую картинку (a = 462, b = 1071):