Наименьшее общее кратное python

В Python есть несколько способов найти наименьшее общее кратное (НОК) двух или более чисел.

1. Используя функцию Math. lcm() (Python 3.9+)

Начиная с Python 3.9, модуль math включает функцию math. lcm(), которая напрямую вычисляет НОК одного или нескольких целых чисел. Это самый простой и рекомендуемый способ.

Import math

Num1 = 12

Num2 = 18

Lcm = math. lcm(num1, num2)

Print(f"НОК({num1}, {num2}) = {lcm}") # Output: НОК(12, 18) = 36

# Для нескольких чисел:

Numbers = [12, 18, 24]

Lcm = math. lcm(*numbers) # Используем распаковку аргументов (*)

Print(f"НОК({numbers}) = {lcm}") # Output: НОК([12, 18, 24]) = 72

2. Реализация функции Lcm() (для Python < 3.9 или для понимания алгоритма)

Если вы используете более старую версию Python или хотите понять, как вычисляется НОК, вы можете реализовать функцию самостоятельно. Для этого обычно используется формула, связывающая НОК и наибольший общий делитель (НОД):

НОК(a, b) = (|a * b|) / НОД(a, b)

Вот реализация:

Import math

Def gcd(a, b):

"""Вычисляет наибольший общий делитель (НОД) двух чисел."""

while b:

a, b = b, a % b

return a

Def lcm(a, b):

"""Вычисляет наименьшее общее кратное (НОК) двух чисел."""

return abs(a*b) // gcd(a, b) # abs — для корректной работы с отрицательными числами, // — целочисленное деление

Num1 = 12

Num2 = 18

Lcm_result = lcm(num1, num2)

Print(f"НОК({num1}, {num2}) = {lcm_result}") # Output: НОК(12, 18) = 36

Gcd(a, b): Вычисляет наибольший общий делитель (НОД) двух чисел, используя алгоритм Евклида. Lcm(a, b): Вычисляет наименьшее общее кратное (НОК) двух чисел, используя формулу НОК(a, b) = (|a * b|) / НОД(a, b). abs(a*b): Используется модуль произведения, чтобы функция корректно работала и с отрицательными числами. //: Используется целочисленное деление, чтобы избежать получения результата с плавающей точкой.

3. НОК для нескольких чисел (используя реализацию Lcm()):

Если вам нужно вычислить НОК для более чем двух чисел, вы можете использовать рекурсивный подход:

Import math

Def gcd(a, b):

"""Вычисляет наибольший общий делитель (НОД) двух чисел."""

while b:

a, b = b, a % b

return a

Def lcm(a, b):

"""Вычисляет наименьшее общее кратное (НОК) двух чисел."""

return abs(a*b) // gcd(a, b)

Def lcm_multiple(numbers):

"""Вычисляет НОК для списка чисел."""

if not numbers:

return 1 # НОК Пустого Списка — 1

result = numbers[0]

for i in range(1, len(numbers)):

result = lcm(result, numbers[i])

return result

Numbers = [12, 18, 24]

Lcm_result = lcm_multiple(numbers)

Print(f"НОК({numbers}) = {lcm_result}") # Output: НОК([12, 18, 24]) = 72

Lcm_multiple(numbers): Рекурсивно вычисляет НОК для списка чисел. Начинает с первого числа и вычисляет НОК с каждым последующим числом в списке.

Какой способ использовать?

Python 3.9+: Используйте math. lcm(). Это самый простой, эффективный и рекомендуемый способ. Python < 3.9: Реализуйте функции gcd() и lcm() (как показано во втором примере) или используйте сторонние библиотеки, если они у вас уже установлены. Если вам нужно вычислить НОК для более чем двух чисел, используйте lcm_multiple().

Дополнительные замечания:

Отрицательные числа: Функции, представленные здесь, корректно обрабатывают отрицательные числа, возвращая положительное значение НОК. Большие числа: Python может работать с произвольно большими целыми числами, поэтому эти функции будут работать и для больших чисел (ограничения могут быть связаны только с доступной памятью). Эффективность: Для очень больших списков чисел или очень больших чисел могут существовать более эффективные алгоритмы, но для большинства практических случаев представленные выше решения вполне достаточны. Fractions. gcd() (устарело): В Python 3.5 и ранее для вычисления НОД использовалась функция fractions. gcd(). Она была объявлена устаревшей и удалена в Python 3.9. Вместо нее следует использовать math. gcd().