Najmniejsza wspólna wielokrotność
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:
- Rozłożyć liczby na iloczyn czynników pierwszych (instrukcja jak rozkładać na czynniki pierwsze)
- Dla każdego czynnika sprawdzić ile razy wystąpił dla jednej i drugiej liczby. Wybrać większą wartość i tyle razy zapisać tę liczbę.
- 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:
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
int a, b, iloczyn;
cout << "Podaj pierwsza liczbe: ";
cin >> a;
cout << "Podaj druga liczbe: ";
cin >> b;
iloczyn = a * b;
while(a != b)
{
if(a > b) {
a = a - b;
} else {
b = b - a;
}
}
cout << "Najmniejsza wspolna wielokrotnosc: " << iloczyn/a << endl;
system("PAUSE >nul");
return 0;
}
