Beräkna och få fram största gemensamma divisor och minsta gemensamma multipel i Python

Företag

Nedan beskrivs hur man beräknar och får fram den största gemensamma divisorn och den minsta gemensamma multipeln i Python.

  • Den största gemensamma divisorn och den minsta gemensamma multipeln av två heltal
  • Den största gemensamma divisorn och den minsta gemensamma multipeln av tre eller flera heltal.

Observera att specifikationerna för de funktioner som finns i standardbiblioteket skiljer sig åt beroende på Python-versionen. En exempelimplementering av en funktion som inte finns i standardbiblioteket visas också i den här artikeln.

  • Python 3.4 eller tidigare
    • GCD:fractions.gcd()(endast två argument)
  • Python 3.5 eller senare
    • GCD:math.gcd()(endast två argument)
  • Python 3.9 eller senare
    • GCD:math.gcd()(stöder mer än tre argument)
    • minsta gemensamma nämnare:math.lcm()(stöder mer än tre argument)

Här förklarar vi metoden med hjälp av standardbiblioteket Python; NumPy kan enkelt användas för att beräkna den största gemensamma divisorn och den minsta gemensamma multipeln för varje element i flera matriser.

Den största gemensamma divisorn och den minsta gemensamma multipeln av två heltal

GCD

Sedan Python 3.5 finns funktionen gcd() i matematikmodulen. gcd() är en akronym för

  • greatest common divisor

Återger den största gemensamma divisorn för det heltal som anges i argumentet.

import math

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

Observera att i Python 3.4 och tidigare finns funktionen gcd() i modulen fractions, inte i modulen math. fractions måste importeras och fractions.gcd().

minsta gemensamma nämnare

Funktionen lcm(), som returnerar den minsta gemensamma multipeln, lades till i matematikmodulen i Python 3.9. lcm är en akronym för

  • least common multiple

Återger den minsta gemensamma multipeln av det heltal som anges i argumentet.

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

Före Python 3.8 finns inte lcm(), men kan enkelt beräknas med gcd().

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

Exempel på genomförande.

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

print(my_lcm(6, 4))
# 12

/Eftersom detta resulterar i ett decimalfloat används två backslashes för att avbryta decimalpunkten och återge ett heltalsdivisionsresultat. Observera att ingen bearbetning görs för att avgöra om argumentet är ett heltal eller inte.

Den största gemensamma divisorn och den minsta gemensamma multipeln av tre eller flera heltal.

Python 3.9 eller senare

Från och med Python 3.9 har alla följande funktioner stöd för fler än tre argument.

  • 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

*Om du vill beräkna den största gemensamma divisorn eller den minsta gemensamma multipeln av elementen i en lista anger du argumentet med detta.

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

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

Python 3.8 eller tidigare

Före Python 3.8 hade funktionen gcd() endast två argument.

För att hitta den största gemensamma divisorn eller den minsta gemensamma multipeln av tre eller flera heltal krävs ingen särskilt komplicerad algoritm; det räcker med att beräkna den största gemensamma divisorn eller den minsta gemensamma multipeln för vart och ett av multipelvärdena i tur och ordning med hjälp av den överordnade funktionen 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

Observera att före Python 3.4 finns funktionen gcd() i fraktionsmodulen, inte i matematikmodulen.

minsta gemensamma nämnare

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