Slijedi opis kako izračunati i dobiti najveći zajednički djelitelj i najmanji zajednički višekratnik u Pythonu.
- Najveći zajednički djelitelj i najmanji zajednički višekratnik dvaju cijelih brojeva
- Najveći zajednički djelitelj i najmanji zajednički višekratnik tri ili više cijelih brojeva
Imajte na umu da se specifikacije funkcija koje se nalaze u standardnoj biblioteci razlikuju ovisno o verziji Pythona. Primjer implementacije funkcije koja nije u standardnoj biblioteci također je prikazan u ovom članku.
- Python 3.4 ili stariji
- GCD:
fractions.gcd()(samo dva argumenta)
- GCD:
- Python 3.5 ili noviji
- GCD:
math.gcd()(samo dva argumenta)
- GCD:
- Python 3.9 ili noviji
- GCD:
math.gcd()(podržava više od tri argumenta) - najmanji zajednički nazivnik:
math.lcm()(podržava više od tri argumenta)
- GCD:
Ovdje objašnjavamo metodu korištenjem standardne Python biblioteke; NumPy se lako može koristiti za izračunavanje najvećeg zajedničkog djelitelja i najmanjeg zajedničkog višekratnika za svaki element višestrukih nizova.
Najveći zajednički djelitelj i najmanji zajednički višekratnik dvaju cijelih brojeva
GCD
Od Pythona 3.5, u matematičkom modulu postoji funkcija gcd(). gcd() je akronim za
- greatest common divisor
Vraća najveći zajednički djelitelj cijelog broja navedenog u argumentu.
import math
print(math.gcd(6, 4))
# 2
Imajte na umu da je u Pythonu 3.4 i ranijim verzijama funkcija gcd() u modulu razlomaka, a ne u modulu matematike. razlomci moraju biti uvezeni i razlomci.gcd().
najmanji zajednički nazivnik
Funkcija lcm() koja vraća najmanji zajednički višekratnik dodana je u matematički modul u Pythonu 3.9. lcm je akronim za
- least common multiple
Vraća najmanji zajednički višekratnik cijelog broja navedenog u argumentu.
print(math.lcm(6, 4))
# 12
Prije Pythona 3.8, lcm() nije osiguran, ali se može lako izračunati pomoću gcd().
lcm(a, b) = a * b / gcd(a, b)
Primjer implementacije.
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
print(my_lcm(6, 4))
# 12
/Budući da to rezultira decimalnim float-om, dvije obrnute kose crte koriste se za skraćivanje decimalne točke i vraćanje rezultata dijeljenja cijelog broja. Imajte na umu da se ne obrađuje kako bi se utvrdilo je li argument cijeli broj ili ne.
Najveći zajednički djelitelj i najmanji zajednički višekratnik tri ili više cijelih brojeva
Python 3.9 ili noviji
Počevši od Pythona 3.9, sve sljedeće funkcije podržavaju više od tri argumenta.
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
*Ako želite izračunati najveći zajednički djelitelj ili najmanji zajednički višekratnik elemenata popisa, navedite argument s ovim.
l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3
print(math.lcm(*l))
# 54
Python 3.8 ili stariji
Prije Pythona 3.8, funkcija gcd() podržavala je samo dva argumenta.
Za pronalaženje najvećeg zajedničkog djelitelja ili najmanjeg zajedničkog višekratnika tri ili više cijelih brojeva nije potreban posebno kompliciran algoritam; samo izračunajte najveći zajednički djelitelj ili najmanji zajednički višekratnik za svaku od višestrukih vrijednosti zauzvrat koristeći funkciju višeg reda reducirati().
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
Opet, imajte na umu da je prije Pythona 3.4, funkcija gcd() bila u modulu razlomaka, a ne u matematičkom modulu.
najmanji zajednički nazivnik
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
