LCM algorithm

W przypadku małych liczb, najmniejszą wspólną wielokrotność można znaleźć wypisując wielokrotności podanych liczb. Dla dużych liczb znajdowanie NWW tą metodą byłoby bardzo czasochłonne. W takim przypadku należy skorzystać z poniższego algorytmu.
Algorytm NWW
  • Rozkładamy obie liczby na iloczyn czynników pierwszych,
  • Dla każdego czynnika pierwszego sprawdzamy w którym rozkładzie wystąpił większą liczbę razy i wypisujemy go taką liczbę razy
  • Wymnażamy wszystkie wypisane liczby, otrzymując w rezultacie szukaną NWW.
Wyznacz najmniejszą wspólną wielokrotność liczb \(54\) i \(76\).
Rozkładamy obie liczby na iloczyn czynników pierwszych: \[ 54 = 2 \cdot 3 \cdot 3 \cdot 3\\[6pt] 76 = 2 \cdot 2 \cdot 19 \] Teraz patrzymy ile razy wystąpiły poszczególne liczby pierwsze w każdym z rozkładów:
  • Liczba \(2\) wystąpiła raz w I rozkładzie i dwa razy w II rozkładzie. Zatem wypisujemy ją dwa razy.
  • Liczba \(3\) wystąpiła trzy w I rozkładzie i ani razu w II rozkładzie. Zatem wypisujemy ją trzy razy.
  • Liczba \(19\) nie wystąpiła w I rozkładzie i wystąpiła raz w II rozkładzie. Zatem wypisujemy ją jeden raz.
Zatem nasze wypisane kolejno liczby, to: \[2, 2, 3, 3, 3, 19.\] Czyli NWW obliczmy licząc ich iloczyn: \[\operatorname{NWW}(54, 76) = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 \cdot 19 = 2052\]
Previous topic
Irrational numbers