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

Найти наибольший общий делитель двух чисел можно разными способами. Сегодня один из них! Простой!
Программа
# Нахождение НОД (наибольший общий делитель) для А и Б больше нуля.
# При нуле одного второй автоматически становится НОДом.
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()
Результат работы программы.

Исходник программы:
Еще алгоритмы тут: Школьный уровень.
Комментарии
Отправить комментарий