Poniżej opisano sposób obliczania i uzyskiwania największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności w języku Python.
- Największy wspólny dzielnik i najmniejsza wspólna wielokrotność dwóch liczb całkowitych
- Największy wspólny dzielnik i najmniejsza wspólna wielokrotność trzech lub więcej liczb całkowitych
Należy pamiętać, że specyfikacje funkcji udostępnianych w bibliotece standardowej różnią się w zależności od wersji Pythona. W artykule przedstawiono również przykładową implementację funkcji, która nie znajduje się w bibliotece standardowej.
- Python 3.4 lub wcześniejszy
- GCD:
fractions.gcd()(tylko dwa argumenty)
- GCD:
- Python 3.5 lub nowszy
- GCD:
math.gcd()(tylko dwa argumenty)
- GCD:
- Python 3.9 lub nowszy
- GCD:
math.gcd()(obsługuje więcej niż trzy argumenty) - …:
math.lcm()(obsługuje więcej niż trzy argumenty)
- GCD:
Wyjaśniamy tutaj metodę wykorzystującą standardową bibliotekę Pythona; NumPy można łatwo wykorzystać do obliczania największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności dla każdego elementu wielu tablic.
Największy wspólny dzielnik i najmniejsza wspólna wielokrotność dwóch liczb całkowitych
GCD
Od wersji 3.5 Pythona w module math znajduje się funkcja gcd(). gcd() jest skrótem od
- greatest common divisor
Zwraca największy wspólny dzielnik liczby całkowitej podanej w argumencie.
import math
print(math.gcd(6, 4))
# 2
Należy pamiętać, że w Pythonie 3.4 i wcześniejszych funkcja gcd() znajduje się w module fractions, a nie w module math. należy zaimportować fractions i fractions.gcd().
…
Funkcja lcm(), która zwraca najmniejszą wspólną wielokrotność, została dodana do modułu matematycznego w Pythonie 3.9. lcm jest akronimem od
- least common multiple
Zwraca najmniejszą wspólną wielokrotność liczby całkowitej podanej w argumencie.
print(math.lcm(6, 4))
# 12
Przed wersją Pythona 3.8 funkcja lcm() nie jest dostępna, ale można ją łatwo obliczyć za pomocą funkcji gcd().
lcm(a, b) = a * b / gcd(a, b)
Przykład wdrożenia.
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
# 12
/Ponieważ wynikiem jest liczba zmiennoprzecinkowa, do obcięcia przecinka dziesiętnego i zwrócenia wyniku dzielenia na liczby całkowite zostaną użyte dwa ukośniki odwrotne. Zauważ, że nie jest wykonywane żadne przetwarzanie w celu określenia, czy argument jest liczbą całkowitą, czy nie.
Największy wspólny dzielnik i najmniejsza wspólna wielokrotność trzech lub więcej liczb całkowitych
Python 3.9 lub nowszy
Począwszy od wersji 3.9 Pythona, wszystkie poniższe funkcje obsługują więcej niż trzy argumenty.
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
*Jeśli chcesz obliczyć największy wspólny dzielnik lub najmniejszą wspólną wielokrotność elementów listy, podaj ten argument.
l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3
print(math.lcm(*l))
# 54
Python 3.8 lub wcześniejszy
Przed wersją Pythona 3.8 funkcja gcd() miała tylko dwa argumenty.
Aby znaleźć największy wspólny dzielnik lub najmniejszą wspólną wielokrotność trzech lub więcej liczb całkowitych, nie jest potrzebny żaden szczególnie skomplikowany algorytm. Wystarczy obliczyć największy wspólny dzielnik lub najmniejszą wspólną wielokrotność dla każdej z wartości wielokrotności po kolei za pomocą funkcji wyższego rzędu 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
Zwróć uwagę, że przed wersją 3.4 Pythona funkcja gcd() znajduje się w module fraction, a nie w module math.
…
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