Изчисляване и получаване на най-големия общ делител и най-малкото общо кратно в Python

Бизнес

По-долу е описано как да изчислите и получите най-големия общ делител и най-малкото общо кратно в Python.

  • Най-голям общ делител и най-малко общо кратно на две цели числа
  • Най-голям общ делител и най-малко общо кратно на три или повече цели числа

Обърнете внимание, че спецификациите на функциите, предоставени в стандартната библиотека, се различават в зависимост от версията на Python. В тази статия е показана и примерна реализация на функция, която не е в стандартната библиотека.

  • Python 3.4 или по-ранна версия
    • GCD:fractions.gcd()(само два аргумента)
  • Python 3.5 или по-нова версия
    • GCD:math.gcd()(само два аргумента)
  • Python 3.9 или по-нова версия
    • GCD:math.gcd()(поддържа повече от три аргумента)
    • най-малък общ знаменател:math.lcm()(поддържа повече от три аргумента)

Тук ще обясним метода, като използваме стандартната библиотека на Python; NumPy може лесно да се използва за изчисляване на най-големия общ делител и най-малкото общо кратно за всеки елемент от множество масиви.

Най-голям общ делител и най-малко общо кратно на две цели числа

GCD

От версия 3.5 на Python в модула math има функция gcd(). gcd() е акроним на

  • greatest common divisor

Връща най-големия общ делител на цялото число, посочено в аргумента.

import math

print(math.gcd(6, 4))
# 2

Имайте предвид, че в Python 3.4 и по-ранни версии функцията gcd() е в модула fractions, а не в модула math. fractions трябва да се импортира и fractions.gcd().

най-малък общ знаменател

Функцията lcm(), която връща най-малкото общо кратно, беше добавена към модула Math в Python 3.9. lcm е акроним на

  • least common multiple

Връща най-малкото общо кратно на цялото число, посочено в аргумента.

print(math.lcm(6, 4))
# 12

Преди версия 3.8 на Python не е предоставена функцията 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 или по-нова версия

От версия 3.9 на Python всички следващи функции поддържат повече от три аргумента.

  • 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 или по-ранна версия

Преди версия 3.8 на Python функцията 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

Отново имайте предвид, че преди версия 3.4 на Python функцията 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
Copied title and URL