Введение
В данной статье рассмотрим три способа найти наибольший общий делитель (НОД) в Python.
Использование функции math.gcd()
Для нахождения НОД мы можем воспользоваться готовой функцией gcd() из встроенного модуля math.
Синтаксис функции math.gcd():
import math
math.gcd(int1, int2)
# Возвращает наибольший общий делитель двух целых чисел int1 и int2Примеры:
import math
print(math.gcd(3, 6)) # Вывод: 3
print(math.gcd(6, 12)) # Вывод: 6
print(math.gcd(12, 36)) # Вывод: 12
print(math.gcd(-12, -36)) # Вывод: 12
print(math.gcd(5, 12)) # Вывод: 1
print(math.gcd(10, 0)) # Вывод: 10
print(math.gcd(0, 34)) # Вывод: 34
print(math.gcd(0, 0)) # Вывод: 0Использование алгоритма Евклида
Ещё, для нахождения НОД мы можем воспользоваться алгоритмом Евклида, который предназначен как раз для этого.
Для его реализации, сначала дадим пользователю возможность ввести два числа.
a = int(input('Введите первое число: '))
b = int(input('Введите второе число: '))Теперь создадим цикл while, который не закончится пока числа в переменных a и b не равны нулю.
a = int(input('Введите первое число: '))
b = int(input('Введите второе число: '))
while a != 0 and b != 0:Внутри цикла добавим условие, что если число в переменной a больше числа в переменной b, то к переменной a присвоим остаток от деления a на b, иначе к переменной b будет присвоен остаток от деления b на a.
a = int(input('Введите первое число: '))
b = int(input('Введите второе число: '))
while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % aПосле цикла будет выведена сумма чисел переменных a и b.
a = int(input('Введите первое число: '))
b = int(input('Введите второе число: '))
while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % aПримеры:
# Первая проверка
# Введите первое число: 5
# Введите второе число: 10
# 5
# Вторая проверка
# Введите первое число: 5
# Введите второе число: 12
# 1
# Третья проверка
# Введите первое число: 0
# Введите второе число: 34
# 34Использование рекурсивного алгоритма Евклида
Ещё мы можем использовать рекурсивный алгоритм Евклида для нахождения НОД. Для этого создадим функцию, которую назовём gcd_recursive() и в качестве параметров укажем a и b.
def gcd_recursive(a, b):Внутри функции добавим условие, что если число в переменной b равняется нулю, то вернётся переменная a. Иначе — функция рекурсивно вызовет сама себя и в качестве аргумента a передаст b, а в качестве аргумента b — остаток от деления a на b:
def gcd_recursive(a, b):
if b == 0:
return a
else:
return gcd_recursive(b, a % b)Дадим пользователю возможность ввести два числа, вызовем функцию gcd_recursive() и выведем результат.
def gcd_recursive(a, b):
if b == 0:
return a
else:
return gcd_recursive(b, a % b)
a = int(input('Введите первое число: '))
b = int(input('Введите второе число: '))
gcd_recursive_result = gcd_recursive(a, b)
print(f"НОД чисел {a} и {b}: {gcd_recursive_result}")Примеры:
# Первая проверка
# Введите первое число: 24
# Введите второе число: 36
# НОД чисел 24 и 36: 12
# Вторая проверка
# Введите первое число: 11
# Введите второе число: 15
# НОД чисел 11 и 15: 1Заключение
В ходе статьи мы с Вами разобрали целых три способа поиска наибольшего общего делителя (НОД) в Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂
