Как найти наибольший общий делитель (НОД) в Python

НОД — это наибольший общий делитель. Наибольший общий делитель чисел a и b — это наибольшее число, на которое делятся числа a и b без остатка.

Найти наибольший общий делитель двух чисел можно разными способами. Сегодня один из них! Простой!


Программа

# Нахождение НОД (наибольший общий делитель) для  А и Б больше нуля.
# При нуле одного второй автоматически становится НОДом.

def nod(a,b:int):

    # Оба параметра нули.
    if ((a==0) and (b==0)):
        print('Oшибка параметров! Числа равны нулю!')
        return None

    # Параметры функции должны быть положительными
    if ((a<0) or (b<0)):
        print('Oшибка параметров! Один или оба отрицательны!')
        return None

    # Один из параметров равен нулю, тогда второй и есть НОД.
    if a==0:
        return b
    if b==0:
        return a

    # НОД не может быть больше минимального из двух
    if a>b:
        max_tmp_nod=b
    else:
        max_tmp_nod=a

    # НОД не может быть больше половины от минимального
    max_tmp_nod = max_tmp_nod//2+1

    # сократили лишнее, а теперь
    # ищем реальный НОД в диапозоне от [2,max_tmp_nod] 
    cur_nod=1
    for i in range(2,max_tmp_nod):

# если оба числа делятся без остатка нашли очередной общий делитель
        if ((a % i == 0) and (b % i == 0)):
            cur_nod=i

# Возвращаем результат       
    if cur_nod>1:
        return cur_nod
    else:
        return 1

# Тестируем программу
def test():
    print('Тест1 - 567 и 444 =',nod(300,111))
    print('Тест2 - 226 и 512 =',nod(900,512))
    print('Тест3 - 600 и 555 =',nod(600,555))
    print('Тест4 -   0 и 123 =',nod(0,123))

# Запускаем программу
test()

Результат работы программы.

Исходник программы:

Cкачать из Облака

Еще алгоритмы тут: Школьный уровень.