Izračunajte in pridobite največji skupni delitelj in najmanjši skupni večkratnik v programu Python

Posel

V nadaljevanju je opisano, kako v programu Python izračunati in dobiti največji skupni delitelj in najmanjši skupni večkratnik.

  • Največji skupni delitelj in najmanjši skupni večkratnik dveh celih števil
  • Največji skupni delitelj in najmanjši skupni večkratnik treh ali več celih števil

Upoštevajte, da se specifikacije funkcij v standardni knjižnici razlikujejo glede na različico Pythona. V tem članku je prikazan tudi primer implementacije funkcije, ki ni v standardni knjižnici.

  • Python 3.4 ali starejša različica
    • GCD:fractions.gcd()(samo dva argumenta)
  • Python 3.5 ali novejši
    • GCD:math.gcd()(samo dva argumenta)
  • Python 3.9 ali novejši
    • GCD:math.gcd()(podpira več kot tri argumente)
    • najmanjši skupni imenovalec:math.lcm()(podpira več kot tri argumente)

Na tem mestu razlagamo metodo z uporabo standardne knjižnice Python; NumPy lahko preprosto uporabite za izračun največjega skupnega delitelja in najmanjšega skupnega večkratnika za vsak element več polj.

Največji skupni delitelj in najmanjši skupni večkratnik dveh celih števil

GCD

Od različice Python 3.5 je v matematičnem modulu funkcija gcd(). gcd() je kratica za

  • greatest common divisor

Vrne največji skupni delitelj celega števila, navedenega v argumentu.

import math

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

Upoštevajte, da je funkcija gcd() v Pythonu 3.4 in prejšnjih različicah v modulu fractions in ne v modulu math. fractions je treba uvoziti in fractions.gcd().

najmanjši skupni imenovalec

Funkcija lcm(), ki vrne najmanjši skupni večkratnik, je bila dodana matematičnemu modulu v Pythonu 3.9. lcm je kratica za

  • least common multiple

Vrne najmanjši skupni mnogokratnik celega števila, navedenega v argumentu.

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

Pred različico Python 3.8 funkcija lcm() ni na voljo, vendar jo je mogoče preprosto izračunati s funkcijo gcd().

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

Primer izvajanja.

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

print(my_lcm(6, 4))
# 12

/Ker je rezultat decimalni spremenljivec, se uporabita dva povratna lomljenca, da se okrni decimalna vejica in vrne celoštevilski rezultat deljenja. Upoštevajte, da se ne opravi nobena obdelava za določitev, ali je argument celo število ali ne.

Največji skupni delitelj in najmanjši skupni večkratnik treh ali več celih števil

Python 3.9 ali novejši

Od različice Python 3.9 naprej vse naslednje funkcije podpirajo več kot tri argumente.

  • 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

*Če želite izračunati največji skupni delitelj ali najmanjši skupni mnogokratnik elementov seznama, navedite argument s tem.

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

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

Python 3.8 ali starejša različica

Funkcija gcd() je pred različico Python 3.8 podpirala le dva argumenta.

Za iskanje največjega skupnega delitelja ali najmanjšega skupnega večkratnika treh ali več celih števil ni potreben posebej zapleten algoritem; preprosto izračunajte največji skupni delitelj ali najmanjši skupni večkratnik za vsako od vrednosti večkratnika po vrsti z uporabo funkcije višjega reda 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

Upoštevajte, da je funkcija gcd() pred različico Python 3.4 v modulu fraction in ne v modulu math.

najmanjši skupni imenovalec

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