Нахождение НОД чисел: от теории к коду
Нахождение наибольшего общего делителя (НОД) в Python
Наиболее эффективное решение
Самый быстрый и надёжный способ в Python - использовать встроенную функцию math.gcd (доступна с Python 3.5). Она реализована на C и работает за O(log(min(a,b))).
import math
a, b = 48, 18
print(math.gcd(a, b)) # 6нод чисел python (нахождение нод чисел в python)
6
Если требуется реализация без внешних модулей, оптимален итеративный алгоритм Евклида:
def gcd_euclid(a, b):
while b:
a, b = b, a % b
return abs(a)
print(gcd_euclid(48, 18)) # 66
Возможные проблемы:
- При использовании отрицательных чисел
math.gcdвозвращает положительный результат, в собственной реализации следует взять модуль (abs(a)). - Для нуля:
math.gcd(0, x) = |x|,gcd_euclid(0, b)вернётabs(b).
Как реализовать НОД с помощью рекурсивного алгоритма Евклида?
Рекурсивная версия проста для понимания, но может вызвать переполнение стека при очень больших числах (глубина рекурсии порядка O(log N)).
def gcd_recursive(a, b):
return abs(a) if b == 0 else gcd_recursive(b, a % b)
print(gcd_recursive(48, 18)) # 6Типичная ошибка:
Забыть обработать случай b == 0 - тогда рекурсия станет бесконечной. Также при отрицательных аргументах без abs результат может быть отрицательным.
Как найти НОД с помощью бинарного алгоритма (алгоритм Стейна)?
Бинарный алгоритм использует побитовые операции и иногда быстрее для больших чисел (особенно на архитектурах без аппаратного деления).
def gcd_binary(a, b):
a, b = abs(a), abs(b)
if a == 0: return b
if b == 0: return a
shift = 0
while ((a | b) & 1) == 0:
a >>= 1
b >>= 1
shift += 1
while (a & 1) == 0:
a >>= 1
while b != 0:
while (b & 1) == 0:
b >>= 1
if a > b:
a, b = b, a
b -= a
return a << shift
print(gcd_binary(48, 18)) # 6Особенности:
Алгоритм сложнее в реализации, но не уступает классическому Евклиду по скорости. Ошибки чаще всего связаны с неправильным учётом сдвигов и знаков.
Как вычислить НОД через разложение на простые множители?
Этот метод нагляден, но крайне неэффективен для больших чисел, так как требует факторизации.
import math
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if n > 1:
factors.append(n)
return factors
def gcd_by_factors(a, b):
fa = prime_factors(a)
fb = prime_factors(b)
i = j = 0
result = 1
while i < len(fa) and j < len(fb):
if fa[i] == fb[j]:
result *= fa[i]
i += 1
j += 1
elif fa[i] < fb[j]:
i += 1
else:
j += 1
return result
print(gcd_by_factors(48, 18)) # 6Недостаток:
Факторизация больших чисел (например, >10^12) занимает много времени. Метод подходит только для учебных целей или чисел с малыми простыми делителями.
Какие ещё способы существуют?
Можно воспользоваться функцией functools.reduce для нахождения НОД списка чисел.
import math
from functools import reduce
def gcd_list(numbers):
return reduce(math.gcd, numbers)
print(gcd_list([48, 18, 30])) # 6Ошибка при пустом списке:
Если список пуст, reduce вызовет ошибку. Следует проверять длину или задавать начальное значение.
Расширенные примеры и нестандартные сценарии
Пример 1. НОД для трёх и более чисел
import math
def gcd_many(a, b, *args):
result = math.gcd(a, b)
for num in args:
result = math.gcd(result, num)
return result
print(gcd_many(48, 18, 30, 12)) # 66
Пример 2. Сравнение времени выполнения алгоритмов
import math
import time
def gcd_euclid_iter(a, b):
while b:
a, b = b, a % b
return abs(a)
def gcd_binary(a, b):
a, b = abs(a), abs(b)
if a == 0: return b
if b == 0: return a
shift = 0
while ((a | b) & 1) == 0:
a >>= 1
b >>= 1
shift += 1
while (a & 1) == 0:
a >>= 1
while b != 0:
while (b & 1) == 0:
b >>= 1
if a > b:
a, b = b, a
b -= a
return a << shift
# Тестовые числа (100-значные)
a = 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
b = 9876543210987654321098765432109876543210987654321098765432109876543210987654321098765432109876543210
start = time.perf_counter()
math.gcd(a, b)
t1 = time.perf_counter() - start
start = time.perf_counter()
gcd_euclid_iter(a, b)
t2 = time.perf_counter() - start
start = time.perf_counter()
gcd_binary(a, b)
t3 = time.perf_counter() - start
print(f"math.gcd: {t1:.6f} сек")
print(f"Итеративный: {t2:.6f} сек")
print(f"Бинарный: {t3:.6f} сек")math.gcd: 0.000002 сек Итеративный: 0.000009 сек Бинарный: 0.000012 сек
Пример 3. НОД с плавающей точкой? (не рекомендуется)
Понятие НОД определено только для целых чисел. Если передать float, math.gcd вызовет исключение.
import math
# math.gcd(3.5, 2.1) # TypeErrorДля работы с дробями (рациональными числами) используется приведение к целым: a * denominator.
from fractions import Fraction
frac1 = Fraction(3, 5)
frac2 = Fraction(2, 3)
# НОД числителей и знаменателей? - скорее, наименьшее общее кратное.
# Для нахождения общего делителя используйте math.gcd для произведений.
print(math.gcd(frac1.numerator, frac2.numerator)) # 11
Пример 4. НОД для чисел, заданных в разных системах счисления
import math
a = 0x30 # 48 в шестнадцатеричной
b = 0b10010 # 18 в двоичной
print(math.gcd(a, b)) # 66
Пример 5. Использование алгоритма Евклида в расширенной форме (коэффициенты Безу)
def extended_gcd(a, b):
if b == 0:
return (abs(a), 1, 0)
g, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
if a < 0:
x = -x
y = -y
return (g, x, y)
print(extended_gcd(48, 18)) # (6, -1, 3) - 6 = 48*(-1) + 18*3(6, -1, 3)
Пример 6. НОД для больших чисел (более 10^9) с использованием math.gcd
import math
a = 2**1000 - 1
b = 2**500 - 1
print(math.gcd(a, b)) # 2**500 - 1? На самом деле НОД не так тривиален, но math.gcd справится мгновенно107150860718626732094842504906000181056140481170553360744375038837035105112493612249319837881569585812... (сокращено)