La seguente è una descrizione di come calcolare e ottenere il massimo comune divisore e il minimo comune multiplo in Python.
- Il massimo comune divisore e il minimo comune multiplo di due numeri interi
- Il massimo comune divisore e il minimo comune multiplo di tre o più numeri interi
Notate che le specifiche delle funzioni fornite nella libreria standard differiscono a seconda della versione di Python. Un esempio di implementazione di una funzione che non è nella libreria standard è anche mostrato in questo articolo.
- Python 3.4 o precedente
- GCD:
fractions.gcd()(solo due argomenti)
- GCD:
- Python 3.5 o successivo
- GCD:
math.gcd()(solo due argomenti)
- GCD:
- Python 3.9 o successivo
- GCD:
math.gcd()(supporta più di tre argomenti) - minimo comune denominatore:
math.lcm()(supporta più di tre argomenti)
- GCD:
Qui spieghiamo il metodo usando la libreria standard di Python; NumPy può essere facilmente usato per calcolare il massimo comune divisore e il minimo comune multiplo per ogni elemento di più matrici.
Il massimo comune divisore e il minimo comune multiplo di due numeri interi
GCD
A partire da Python 3.5, c'è una funzione gcd() nel modulo math. gcd() è un acronimo per
- greatest common divisor
Restituisce il massimo comune divisore dell'intero specificato nell'argomento.
import math
print(math.gcd(6, 4))
# 2
Si noti che in Python 3.4 e precedenti, la funzione gcd() è nel modulo frazioni, non nel modulo math. fractions deve essere importato e fractions.gcd().
minimo comune denominatore
La funzione lcm(), che restituisce il minimo comune multiplo, è stata aggiunta al modulo math in Python 3.9. lcm è un acronimo per
- least common multiple
Restituisce il minimo comune multiplo dell'intero specificato nell'argomento.
print(math.lcm(6, 4))
# 12
Prima di Python 3.8, lcm() non è fornito, ma può essere facilmente calcolato usando gcd().
lcm(a, b) = a * b / gcd(a, b)
Esempio di implementazione.
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
# 12
/Poiché questo risulta in un float decimale, due backslash sono usati per troncare il punto decimale e restituire un risultato di divisione intero. Si noti che non viene fatta alcuna elaborazione per determinare se l'argomento è un intero o meno.
Il massimo comune divisore e il minimo comune multiplo di tre o più numeri interi
Python 3.9 o successivo
A partire da Python 3.9, tutte le seguenti funzioni supportano più di tre argomenti.
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
*Se volete calcolare il massimo comune divisore o il minimo comune multiplo degli elementi di una lista, specificate l'argomento con questo.
l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3
print(math.lcm(*l))
# 54
Python 3.8 o precedente
Prima di Python 3.8, la funzione gcd() supportava solo due argomenti.
Per trovare il massimo comune divisore o il minimo comune multiplo di tre o più numeri interi, non è richiesto un algoritmo particolarmente complicato; basta calcolare il massimo comune divisore o il minimo comune multiplo per ciascuno dei valori multipli a turno usando la funzione di ordine superiore 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
Di nuovo, notate che prima di Python 3.4, la funzione gcd() è nel modulo fraction, non nel modulo math.
minimo comune denominatore
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
