A legnagyobb közös osztó és a legkisebb közös többszörös kiszámítása és kinyerése Pythonban

Üzleti

Az alábbiakban leírjuk, hogyan lehet kiszámítani és megkapni a legnagyobb közös osztót és a legkisebb közös többszöröst Python nyelven.

  • Két egész szám legnagyobb közös osztója és legkisebb közös többszöröse
  • Három vagy több egész szám legnagyobb közös osztója és legkisebb közös többszöröse

Vegye figyelembe, hogy a szabványos könyvtárban található függvények specifikációi a Python verziójától függően eltérnek. Ebben a cikkben egy olyan függvény megvalósítási példája is látható, amely nem szerepel a szabványos könyvtárban.

  • Python 3.4 vagy korábbi verzió
    • GCD:fractions.gcd()(csak két érv)
  • Python 3.5 vagy újabb verzió
    • GCD:math.gcd()(csak két érv)
  • Python 3.9 vagy újabb verzió
    • GCD:math.gcd()(háromnál több érvet támogat)
    • legkisebb közös nevező:math.lcm()(háromnál több érvet támogat)

Itt elmagyarázzuk a módszert a Python szabványos könyvtárának használatával; a NumPy könnyen használható a legnagyobb közös osztó és a legkisebb közös többszörös kiszámítására több tömb minden elemére.

Két egész szám legnagyobb közös osztója és legkisebb közös többszöröse

GCD

A Python 3.5 óta van egy gcd() függvény a matematikai modulban. gcd() egy rövidítés a következő szavakra

  • greatest common divisor

Az argumentumban megadott egész szám legnagyobb közös osztóját adja vissza.

import math

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

Vegyük figyelembe, hogy a Python 3.4 és korábbi verziókban a gcd() függvény a fractions modulban van, nem a math modulban. fractions importálni kell és a fractions.gcd().

legkisebb közös nevező

Az lcm() függvény, amely a legkisebb közös többszörösét adja vissza, a Python 3.9-ben került a matematikai modulba. lcm a következő rövidítése

  • least common multiple

Az argumentumban megadott egész szám legkisebb közös többszörösét adja vissza.

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

A Python 3.8 előtt az lcm() nem áll rendelkezésre, de könnyen kiszámítható a gcd() segítségével.

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

Végrehajtási példa.

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

print(my_lcm(6, 4))
# 12

/Mivel ez egy tizedes lebegőszámot eredményez, két backslashes karaktert használunk a tizedespont lefaragására, és egész szám osztás eredményét adjuk vissza. Megjegyzendő, hogy nem történik semmilyen feldolgozás annak megállapítására, hogy az argumentum egész szám-e vagy sem.

Három vagy több egész szám legnagyobb közös osztója és legkisebb közös többszöröse

Python 3.9 vagy újabb verzió

A Python 3.9-től kezdve a következő függvények mindegyike támogatja a háromnál több argumentumot.

  • 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

*Ha egy lista elemeinek legnagyobb közös osztóját vagy legkisebb közös többszörösét szeretné kiszámítani, adja meg az argumentumot ezzel.

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

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

Python 3.8 vagy korábbi verzió

A Python 3.8 előtt a gcd() függvény csak két argumentumot támogatott.

Három vagy több egész szám legnagyobb közös osztójának vagy legkisebb közös többszörösének megtalálásához nincs szükség különösebben bonyolult algoritmusra; elég, ha a reduce() magasabb rendű függvény segítségével sorban kiszámítjuk a legnagyobb közös osztót vagy legkisebb közös többszöröst minden egyes többszörös értékre.

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

Ismét megjegyezzük, hogy a Python 3.4 előtt a gcd() függvény a tört modulban található, nem a matematikai modulban.

legkisebb közös nevező

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