Beregn og få den største fælles divisor og det mindste fælles multiplum i Python

Forretning

Følgende er en beskrivelse af, hvordan man beregner og får den største fælles divisor og det mindste fælles multiplum i Python.

  • Den største fælles divisor og det mindste fælles multiplum af to hele tal
  • Den største fælles divisor og det mindste fælles multiplum af tre eller flere hele tal

Bemærk, at specifikationerne for de funktioner, der findes i standardbiblioteket, varierer afhængigt af Python-versionen. En eksempelimplementering af en funktion, der ikke findes i standardbiblioteket, er også vist i denne artikel.

  • Python 3.4 eller tidligere
    • GCD:fractions.gcd()(kun to argumenter)
  • Python 3.5 eller nyere
    • GCD:math.gcd()(kun to argumenter)
  • Python 3.9 eller nyere
    • GCD:math.gcd()(understøtter mere end tre argumenter)
    • mindste fællesnævner:math.lcm()(understøtter mere end tre argumenter)

Her forklarer vi metoden ved hjælp af standard Python-biblioteket; NumPy kan nemt bruges til at beregne den største fælles divisor og det mindste fælles multiplum for hvert element i flere arrays.

Den største fælles divisor og det mindste fælles multiplum af to hele tal

GCD

Siden Python 3.5 har der været en gcd()-funktion i matematikmodulet. gcd() er en forkortelse for

  • greatest common divisor

Returnerer den største fælles divisor for det heltal, der er angivet i argumentet.

import math

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

Bemærk, at i Python 3.4 og tidligere er funktionen gcd() i modulet fractions og ikke i math-modulet. fractions skal importeres og fractions.gcd().

mindste fællesnævner

Funktionen lcm(), som returnerer det mindste fælles multiplum, blev tilføjet til matematikmodulet i Python 3.9. lcm er en forkortelse for

  • least common multiple

Returnerer det mindste fælles multiplum af det heltal, der er angivet i argumentet.

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

Før Python 3.8 er lcm() ikke tilgængelig, men kan nemt beregnes ved hjælp af gcd().

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

Gennemførelseseksempel.

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

print(my_lcm(6, 4))
# 12

/Da dette resulterer i et decimalfloat, bruges to backslashes til at afkortes decimalkommaet og returnere et heltalsdivisionsresultat. Bemærk, at der ikke foretages nogen behandling for at afgøre, om argumentet er et heltal eller ej.

Den største fælles divisor og det mindste fælles multiplum af tre eller flere hele tal

Python 3.9 eller nyere

Fra og med Python 3.9 understøtter alle følgende funktioner mere end tre argumenter.

  • 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

*Hvis du ønsker at beregne den største fælles divisor eller det mindste fælles multiplum af elementerne i en liste, skal du angive argumentet med dette.

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

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

Python 3.8 eller tidligere

Før Python 3.8 understøttede funktionen gcd() kun to argumenter.

For at finde den største fælles divisor eller det mindste fælles multiplum af tre eller flere heltal er det ikke nødvendigt med en særlig kompliceret algoritme; du skal blot beregne den største fælles divisor eller det mindste fælles multiplum for hver af multiplumværdierne på skift ved hjælp af funktionen reduce() af højere orden.

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

Bemærk igen, at før Python 3.4 findes funktionen gcd() i fraction-modulet og ikke i math-modulet.

mindste fællesnævner

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