Următoarea este o descriere a modului de calcul și de obținere a celui mai mare divizor comun și a celui mai mic multiplu comun în Python.
- Cel mai mare divizor comun și cel mai mic multiplu comun a doi numere întregi
- Cel mai mare divizor comun și cel mai mic multiplu comun a trei sau mai multe numere întregi
Rețineți că specificațiile funcțiilor furnizate în biblioteca standard diferă în funcție de versiunea Python. În acest articol este prezentat și un exemplu de implementare a unei funcții care nu se află în biblioteca standard.
- Python 3.4 sau anterior
- GCD:
fractions.gcd()(doar două argumente)
- GCD:
- Python 3.5 sau o versiune ulterioară
- GCD:
math.gcd()(doar două argumente)
- GCD:
- Python 3.9 sau o versiune ulterioară
- GCD:
math.gcd()(acceptă mai mult de trei argumente) - cel mai mic numitor comun:
math.lcm()(acceptă mai mult de trei argumente)
- GCD:
Aici explicăm metoda folosind biblioteca standard Python; NumPy poate fi utilizat cu ușurință pentru a calcula cel mai mare divizor comun și cel mai mic multiplu comun pentru fiecare element din mai multe matrici.
Cel mai mare divizor comun și cel mai mic multiplu comun a doi numere întregi
GCD
Începând cu Python 3.5, există o funcție gcd() în modulul math. gcd() este un acronim pentru
- greatest common divisor
Returnează cel mai mare divizor comun al numărului întreg specificat în argument.
import math
print(math.gcd(6, 4))
# 2
Rețineți că, în Python 3.4 și versiunile anterioare, funcția gcd() se află în modulul fracții, nu în modulul matematic. fractions trebuie să fie importată și fractions.gcd().
cel mai mic numitor comun
Funcția lcm(), care returnează cel mai mic multiplu comun, a fost adăugată la modulul math în Python 3.9. lcm este un acronim pentru
- least common multiple
Returnează cel mai mic multiplu comun al numărului întreg specificat în argument.
print(math.lcm(6, 4))
# 12
Înainte de Python 3.8, lcm() nu este furnizat, dar poate fi calculat cu ușurință folosind gcd().
lcm(a, b) = a * b / gcd(a, b)
Exemplu de punere în aplicare.
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
# 12
/Deoarece acest lucru are ca rezultat o zecimală flotantă, se folosesc două backslash-uri pentru a trunchia virgula zecimală și pentru a returna un rezultat de diviziune întreagă. Rețineți că nu se efectuează nicio procesare pentru a determina dacă argumentul este un număr întreg sau nu.
Cel mai mare divizor comun și cel mai mic multiplu comun a trei sau mai multe numere întregi
Python 3.9 sau o versiune ulterioară
Începând cu Python 3.9, toate funcțiile următoare acceptă mai mult de trei 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
*Dacă doriți să calculați cel mai mare divizor comun sau cel mai mic multiplu comun al elementelor unei liste, specificați argumentul cu acest lucru.
l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3
print(math.lcm(*l))
# 54
Python 3.8 sau anterior
Înainte de Python 3.8, funcția gcd() suporta doar două argumente.
Pentru a găsi cel mai mare divizor comun sau cel mai mic multiplu comun a trei sau mai multe numere întregi, nu este nevoie de un algoritm deosebit de complicat; este suficient să se calculeze cel mai mare divizor comun sau cel mai mic multiplu comun pentru fiecare dintre valorile multiple în parte, utilizând funcția de ordin superior 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
Din nou, rețineți că înainte de Python 3.4, funcția gcd() se află în modulul fraction, nu în modulul math.
cel mai mic numitor comun
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