Ostatnie obliczenia

Kalkulator online - Najmniejsza wspólna wielokrotność (NWW)

Tutaj możesz znaleźć nawiększy wspólny dzielnik dwóch liczb.

Podaj liczby dodatnie:

Jak to się robi?

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.

Pytania i komentarze

comments powered by Disqus