Нижче наведено опис того, як обчислити та отримати найбільший спільний дільник і найменше спільне кратне в 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.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
*Якщо ви хочете обчислити найбільший спільний дільник або найменше спільне кратне елементів списку, вкажіть аргумент з цим.
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() була в модулі дробу, а не в математичного модуля.
найменший спільний знаменник
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
