Berechnen und Ermitteln des größten gemeinsamen Teilers und des kleinsten gemeinsamen Vielfachen in Python

Geschäft

Im Folgenden wird beschrieben, wie man in Python den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache berechnet und erhält.

  • Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache von zwei ganzen Zahlen
  • Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache von drei oder mehr ganzen Zahlen

Beachten Sie, dass die Spezifikationen der in der Standardbibliothek enthaltenen Funktionen je nach Python-Version unterschiedlich sind. Eine Beispielimplementierung einer Funktion, die nicht in der Standardbibliothek enthalten ist, wird ebenfalls in diesem Artikel gezeigt.

  • Python 3.4 oder früher
    • GCD:fractions.gcd()(nur zwei Argumente)
  • Python 3.5 oder höher
    • GCD:math.gcd()(nur zwei Argumente)
  • Python 3.9 oder höher
    • GCD:math.gcd()(unterstützt mehr als drei Argumente)
    • kleinster gemeinsamer Nenner:math.lcm()(unterstützt mehr als drei Argumente)

Hier erklären wir die Methode unter Verwendung der Standard-Python-Bibliothek; NumPy kann leicht verwendet werden, um den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache für jedes Element von mehreren Arrays zu berechnen.

Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache von zwei ganzen Zahlen

GCD

Seit Python 3.5 gibt es die Funktion gcd() im Mathematikmodul. gcd() ist ein Akronym für

  • greatest common divisor

Gibt den größten gemeinsamen Teiler der im Argument angegebenen ganzen Zahl zurück.

import math

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

Beachten Sie, dass in Python 3.4 und früher die Funktion gcd() im Modul fractions und nicht im Modul math enthalten ist. fractions muss importiert werden und fractions.gcd().

kleinster gemeinsamer Nenner

Die Funktion lcm(), die das kleinste gemeinsame Vielfache zurückgibt, wurde dem Mathematikmodul in Python 3.9 hinzugefügt. lcm ist ein Akronym für

  • least common multiple

Gibt das kleinste gemeinsame Vielfache der im Argument angegebenen Ganzzahl zurück.

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

Vor Python 3.8 steht lcm() nicht zur Verfügung, kann aber leicht mit gcd() berechnet werden.

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

Beispiel für die Umsetzung.

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

print(my_lcm(6, 4))
# 12

/Da dies zu einer dezimalen Fließkommazahl führt, werden zwei Backslashes verwendet, um den Dezimalpunkt abzuschneiden und ein ganzzahliges Divisionsergebnis zurückzugeben. Beachten Sie, dass keine Verarbeitung erfolgt, um festzustellen, ob das Argument eine ganze Zahl ist oder nicht.

Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache von drei oder mehr ganzen Zahlen

Python 3.9 oder höher

Ab Python 3.9 unterstützen alle der folgenden Funktionen mehr als drei 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

*Wenn Sie den größten gemeinsamen Teiler oder das kleinste gemeinsame Vielfache der Elemente einer Liste berechnen wollen, geben Sie das Argument mit diesem an.

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

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

Python 3.8 oder früher

Vor Python 3.8 unterstützte die Funktion gcd() nur zwei Argumente.

Um den größten gemeinsamen Teiler oder das kleinste gemeinsame Vielfache von drei oder mehr ganzen Zahlen zu finden, ist kein besonders komplizierter Algorithmus erforderlich; es genügt, den größten gemeinsamen Teiler oder das kleinste gemeinsame Vielfache für jeden der Vielfachwerte der Reihe nach mit der übergeordneten Funktion reduce() zu berechnen.

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

Beachten Sie bitte, dass vor Python 3.4 die Funktion gcd() im Modul fraction und nicht im Modul math zu finden ist.

kleinster gemeinsamer Nenner

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