Opis algorytmu
NWW to najmniejsza wspólna wielokrotność dwóch liczb. W przeciwieństwie do wspólnego dzielnika,
interesuje nas najmniejsza wspólna wielokrotność (a nie największa), bo dwie liczby mają nieskończenie wiele wspólnych
wielokrotności. Znalezienie największej z nich jest niemożliwe. NWW to najmniejsza liczba, dla której obie
wyjściowe liczby są dzielnikami.
Aby znaleźć NWW potrzebujemy rozłożyć obie liczby na czynniki pierwsze. Robi się to poprzez dzielenie przez kolejne
liczby pierwsze. Najpierw dzielimy przez 2. Jeżeli choć jedna z liczb, dla których chcemy znaleźć NWW dzieli się
przez 2 bez reszty, wtedy zapisujemy 2 do wyniku i zastępujemy liczbę która się podzieliła wynikiem tego dzielenia.
Wyniki dzielenia znów próbujemy podzielić przez 2. Robimy tak dopóki dzielenie daje wyniki bez reszty dla którejkolwiek
z liczb. Kiedy dla obu liczb dostajemy resztę, wtedy próbujemy podzielić przez 3. Jeżeli któraś z liczb się dzieli bez reszty
przez 3, wtedy zastępujemy ją wynikiem dzielenia i do wyniku trafia 3. Jak dostaniemy reszty dla obu liczb, zaczynamy dzielić
przez 5 i tak dalej. Robimy tak, aż obie liczby w wyniku kolejnych dzieleń będą równe 1. Liczby które zapisywaliśmy (te dla
których udawało nam się dzielić bez reszty) pomnożone przez siebie dają poszukiwaną Najmniejszą Wspólną Wielokrotność.
Przykład
Chcemy znaleźć NWW( 15, 84 ), czyli najmniejszą wspólną wielokrotność liczb 15 i 84. Rozkładamy obie liczby na
czynniki pierwsze. Najpierw próbujemy obie liczby podzielić przez 2. 15 nie dzieli się przez 2, ale 84 już tak:
84 : 2 = 42. Zapamiętujemy 2 do wyniku. Najprościej zapisywać wszystko w tabelce:
| 15 | 84
2 | - | 42
Teraz próbujemy przez 2 podzielić liczby 15 i 42. Dzielenie bez reszty mamy tylko dla 42: 42 : 2 = 21. Zapisujemy więc:
| 15 | 84
2 | - | 42
2 | - | 21
Dalej przez 2 dzielić się już nie da. Zarówno dla 15 jak i 21 dostaniemy resztę. Próbujemy zatem podzielić przez 3. Wynik
takiego dzielenia dla obu liczb jest bez reszty:
| 15 | 84
2 | - | 42
2 | - | 21
3 | 5 | 7
Uzyskane wyniki, tzn 5 i 7, to liczby pierwsze, więc możemy od razu uzupełnić tabelkę do końca:
| 15 | 84
2 | - | 42
2 | - | 21
3 | 5 | 7
5 | 1 | -
7 | - | 1
Jak już wiemy, gdy dostaniemy 1 dla obu liczb zatrzymujemy się. Wynikiem jest iloczyn wszystkich
liczb z pierwszej kolumny dla których dzielenie dawało wynik bez reszty. Mamy więc NWW( 15, 84 ) = 2 * 2 * 3 * 5 * 7 = 420.