Suurimman yhteisen jakajan ja pienimmän yhteisen kertaluvun laskeminen ja saaminen Pythonissa

liiketoiminta

Seuraavassa kuvataan, miten suurin yhteinen jakaja ja pienin yhteinen monikerta lasketaan ja saadaan Pythonilla.

  • Kahden kokonaisluvun suurin yhteinen jakaja ja pienin yhteinen kerrannainen.
  • Kolmen tai useamman kokonaisluvun suurin yhteinen jakaja ja pienin yhteinen kerrannainen.

Huomaa, että standardikirjastossa olevien funktioiden määrittelyt vaihtelevat Python-version mukaan. Tässä artikkelissa esitetään myös esimerkkitoteutus funktiosta, jota ei ole standardikirjastossa.

  • Python 3.4 tai aikaisempi
    • GCD:fractions.gcd()(vain kaksi argumenttia)
  • Python 3.5 tai uudempi
    • GCD:math.gcd()(vain kaksi argumenttia)
  • Python 3.9 tai uudempi
    • GCD:math.gcd()(tukee enemmän kuin kolmea argumenttia)
    • pienin yhteinen nimittäjä:math.lcm()(tukee enemmän kuin kolmea argumenttia)

Tässä selitämme menetelmän käyttämällä Pythonin standardikirjastoa; NumPy:n avulla voidaan helposti laskea suurin yhteinen jakaja ja pienin yhteinen monikerta jokaiselle useiden matriisien elementille.

Kahden kokonaisluvun suurin yhteinen jakaja ja pienin yhteinen kerrannainen.

GCD

Python 3.5:stä lähtien matematiikkamoduulissa on ollut gcd()-funktio. gcd() on lyhenne sanoista

  • greatest common divisor

Palauttaa argumentissa määritetyn kokonaisluvun suurimman yhteisen jakajan.

import math

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

Huomaa, että Python 3.4:ssä ja sitä aikaisemmissa versioissa gcd()-funktio on murtolukumoduulissa, ei matematiikkamoduulissa. fractions on tuotava ja fractions.gcd().

pienin yhteinen nimittäjä

Funktio lcm(), joka palauttaa pienimmän yhteisen kertaluvun, lisättiin matematiikkamoduuliin Python 3.9:ssä. lcm on lyhenne sanoista

  • least common multiple

Palauttaa argumentissa määritetyn kokonaisluvun pienimmän yhteisen kertaluvun.

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

Ennen Python 3.8:a lcm() ei ole käytettävissä, mutta se voidaan helposti laskea käyttämällä gcd():tä.

lcm(a, b) = a * b / gcd(a, b)

Toteutus Esimerkki.

def my_lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(my_lcm(6, 4))
# 12

/Koska tuloksena on desimaalinen liukuluku, käytetään kahta vinoviivaa desimaalipisteen katkaisemiseksi ja kokonaislukujakauman tuloksen palauttamiseksi. Huomaa, että mitään käsittelyä ei tehdä sen määrittämiseksi, onko argumentti kokonaisluku vai ei.

Kolmen tai useamman kokonaisluvun suurin yhteinen jakaja ja pienin yhteinen kerrannainen.

Python 3.9 tai uudempi

Python 3.9:stä lähtien kaikki seuraavat funktiot tukevat enemmän kuin kolmea argumenttia.

  • 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

*Jos haluat laskea listan alkioiden suurimman yhteisen jakajan tai pienimmän yhteisen kertaluvun, määritä argumentti tällä.

l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3

print(math.lcm(*l))
# 54

Python 3.8 tai aikaisempi

Ennen Python 3.8:a gcd()-funktio tuki vain kahta argumenttia.

Kolmen tai useamman kokonaisluvun suurimman yhteisen jakajan tai pienimmän yhteisen kertaluvun löytämiseksi ei tarvita mitään erityisen monimutkaista algoritmia; lasket vain suurimman yhteisen jakajan tai pienimmän yhteisen kertaluvun jokaiselle kertaluvun arvolle vuorollaan käyttämällä ylemmän asteen funktiota 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

Huomaa jälleen, että ennen Python 3.4:ää gcd()-funktio on fraction-moduulissa, ei math-moduulissa.

pienin yhteinen nimittäjä

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