Wyznacza najmniejszą wspólną wielokrotność dwóch liczb korzystając ze wzoru NWW = a·b / NWD.
Najmniejsza wspólna wielokrotność dwóch liczb a i b to najmniejsza dodatnia liczba, która jest wielokrotnością obu liczb jednocześnie.
Przykład: NWW(4, 6) = 12, ponieważ 12 jest pierwszą liczbą, którą można podzielić zarówno przez 4, jak i przez 6.
NWW liczy się przez NWD (Największy Wspólny Dzielnik) ze wzoru:
NWW(a, b) = (a · b) / NWD(a, b)
Dlatego najpierw potrzebujemy funkcji nwd(a, b) – używamy algorytmu Euklidesa, który wielokrotnie zastępuje parę (a, b) parą (b, a mod b), aż druga liczba osiągnie 0.
Uwaga: w zadaniach maturalnych funkcję nwd zazwyczaj trzeba napisać samodzielnie, nie wolno użyć wbudowanej.
funkcja nwd(a, b): dopóki b ≠ 0: pomocnicza ← b b ← a mod b a ← pomocnicza zwróć a funkcja nww(a, b): zwróć (a * b) div nwd(a, b)
def nwd(a, b):
while b != 0:
a, b = b, a % b
return a
def nww(a, b):
return abs(a * b) // nwd(a, b)
# Przykład użycia
print(nww(4, 6))
# Wynik: 12
print(nww(12, 18))
# Wynik: 36
print(nwd(48, 36))
# Wynik: 12O(log min(a,b))O(1)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: