Najmniejsza wspólna wielokrotność C++

Ostatania modyfikacja: 22 kwietnia 2019, kategoria: Matura z informatyki

Najmniejsza wspólna wielokrotność dwóch liczb jest to najmniejsza liczba naturalna, która jest dzielnikiem obydwu tych liczb. Wyznaczanie NWW dla małych liczb jest operacją dość prostą, jednak aby wyznaczyć ją dla dużych liczb niezbędne jest skorzystanie z odpowiednich narzędzi i algorytmów.

Najmniejsza wspólna wielokrotność

Najmniejsza wspólna wielokrotność jest skrótowo opisywana jako NWW. Aby obliczyć NWW danej liczby należy:

  1. Rozłożyć liczby na iloczyn czynników pierwszych
  2. Dla każdego czynnika sprawdzić ile razy wystąpił dla jednej i drugiej liczby. Wybrać większą wartość i tyle razy zapisać tę liczbę.
  3. Wymnożyć wszystkie liczby z punktu poprzedniego.

Rozłożenie liczby na iloczyn czynników pierwszych polega na zapisaniu tej liczby w postaci iloczynu liczb pierwszych. Przykładowo, znajdźmy NWW dla liczb 56 i 100. W pierwszym kroku należy rozłożyć te liczby na czynniki pierwsze:

56 = 2 * 2 * 2 * 7\\
100 = 2 * 2 * 5 * 5\\

Sprawdzamy, ile razy dany czynnik pierwszy został użyty w każdym z równań. Wybieramy największą wartość i tyle razy zapisujemy tę liczbę, czyli:

NWW(56,100) = 2 * 2 * 2 * 5 * 5 * 7 = 1400\\

Algorytm obliczania NWW

Nie istnieje algorytm na obliczanie NWW. Mimo to, dzięki występowaniu tej zależności:

NWW(a,b) =\frac{a*b}{NWD(a,b)}\\

Możemy skorzystać z algorytmu Euklidesa w celu znalezienia największego wspólnego dzielnika NWD. Mając NWD łatwo policzymy NWW.

Kod programu w C++

Oto przykładowy program napisany w C++, umożliwiający wyznaczenie NWW korzystając z algorytmu Euklidesa:

Użytkownik Ocet napisał:

08 kwietnia 2013


Ja bym jeszcze kopsnął linijkę o przypadku względnie pierwszym.

Zachęcam Cię do zostawienia komentarza!

Ilość znaków: 0