Ниже описано, как вычислить и получить наибольший общий делитель и наименьшее общее кратное в Python.
- Наибольший общий делитель и наименьшее общее кратное двух целых чисел
- Наибольший общий делитель и наименьшее общее кратное трех или более целых чисел
Обратите внимание, что спецификации функций, представленных в стандартной библиотеке, отличаются в зависимости от версии Python. Пример реализации функции, не входящей в стандартную библиотеку, также показан в этой статье.
- Python 3.4 или более ранняя версия
- GCD:
fractions.gcd()(только два аргумента)
- GCD:
- Python 3.5 или более поздняя версия
- GCD:
math.gcd()(только два аргумента)
- GCD:
- Python 3.9 или более поздняя версия
- GCD:
math.gcd()(поддерживает более трех аргументов) - наименьший общий знаменатель:
math.lcm()(поддерживает более трех аргументов)
- GCD:
Здесь мы объясним метод с использованием стандартной библиотеки Python; NumPy можно легко использовать для вычисления наибольшего общего делителя и наименьшего общего кратного для каждого элемента нескольких массивов.
Наибольший общий делитель и наименьшее общее кратное двух целых чисел
GCD
Начиная с Python 3.5, в математическом модуле появилась функция gcd(). gcd() — это аббревиатура, означающая
- greatest common divisor
Возвращает наибольший общий делитель целого числа, указанного в аргументе.
import math
print(math.gcd(6, 4))
# 2
Обратите внимание, что в Python 3.4 и более ранних версиях функция gcd() находится в модуле fractions, а не в модуле math. fractions должен быть импортирован и fractions.gcd().
наименьший общий знаменатель
Функция lcm(), которая возвращает наименьшее общее кратное, была добавлена в математический модуль в Python 3.9. lcm — это аббревиатура для
- least common multiple
Возвращает наименьшее общее кратное целого числа, указанного в аргументе.
print(math.lcm(6, 4))
# 12
До версии Python 3.8 функция lcm() не предоставлялась, но ее можно легко вычислить с помощью gcd().
lcm(a, b) = a * b / gcd(a, b)
Пример реализации.
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
# 12
/Поскольку в результате получается десятичное плавающее число, два обратных слеша используются для усечения десятичной точки и возвращения результата целочисленного деления. Обратите внимание, что не производится никакой обработки для определения того, является ли аргумент целым числом или нет.
Наибольший общий делитель и наименьшее общее кратное трех или более целых чисел
Python 3.9 или более поздняя версия
Начиная с Python 3.9, все следующие функции поддерживают более трех аргументов.
math.gcd()math.lcm()
print(math.gcd(27, 18, 9))
# 9
print(math.gcd(27, 18, 9, 3))
# 3
print(math.lcm(27, 9, 3))
# 27
print(math.lcm(27, 18, 9, 3))
# 54
*Если вы хотите вычислить наибольший общий делитель или наименьшее общее кратное элементов списка, укажите аргумент this.
l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3
print(math.lcm(*l))
# 54
Python 3.8 или более ранняя версия
До версии Python 3.8 функция gcd() поддерживала только два аргумента.
Чтобы найти наибольший общий делитель или наименьшее общее кратное трех или более целых чисел, не требуется особенно сложного алгоритма; достаточно вычислить наибольший общий делитель или наименьшее общее кратное для каждого из кратных значений по очереди с помощью функции высшего порядка reduce().
GCD
from functools import reduce
def my_gcd(*numbers):
return reduce(math.gcd, numbers)
print(my_gcd(27, 18, 9))
# 9
print(my_gcd(27, 18, 9, 3))
# 3
l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3
Опять же, обратите внимание, что до Python 3.4 функция gcd() находилась в модуле fraction, а не в модуле math.
наименьший общий знаменатель
def my_lcm_base(x, y):
return (x * y) // math.gcd(x, y)
def my_lcm(*numbers):
return reduce(my_lcm_base, numbers, 1)
print(my_lcm(27, 9, 3))
# 27
print(my_lcm(27, 18, 9, 3))
# 54
l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54
