Najmniejsza Wspólna Wielokrotność, zwykle oznaczana NWW, dwóch liczb a i b to taka liczba c, że jest wielokrotnością a i b. NWW najłatwiej jest wyliczyć znając NWD (Największy Wspólny Dzielnik). W tym artykule zostanie przedstawione jakich algorytmów użyć, aby obliczyć NWW.
Drugi sposób opiera się na fakcie, że NWW musi być podzielna przez jedną jak i drugą liczbę. Początkowo ustalamy NWW jako większą z podanych liczb. Dodajemy do NWW większą wartość tak długo, aż NWW będzie podzielne przez mniejszą liczbę.
Przykładowo dla liczb 2 i 8 obliczenia skończą się w pierszym kroku, ponieważ najpierw za NWW przyjmujemy 8 i sprawdzamy czy jest podzielne przez 2. Jest podzielne, więc zwracamy, że NWW to 8. Co jednak jeśli za NWW przyjmiemy mniejszą liczbę? Otóż wykonamy przez to więcej kroków. Przyjmijmy, że NWW to 2, a następnie sprawdzamy czy jet podzielne przez 8? Nie jest, więc zwiększamy o 2, 4 też nie jest, 6 też nie i dopiero po kolejnym dodaniu otrzymujemy 8 podzielne przez 8.
Algorytm ten jednak nie działa tak szybko, gdy dwie liczby są względnie pierwsze. Przykładem takich liczb jest 4 oraz 11. Wtedy przyjmujemy NWW = 11. Następnie sprawdzamy podzielność przez 4. Nie jest, więc dodajemy 11, 22 nie jest, więc dodajemy 11, 33 nie jest, więc dodajemy 11. NWW = 44, które jest podzielne przez 4, więc jest to NWW.
Najprostszym sposobem jest pomnożenie podanych liczb, a następnie podzielenie ich przez NWD. Metoda ta działa, ponieważ NWW dwóch liczb względnie pierwszych to ich iloczyn. Dzieląc każdą liczbę z osobna przez ich NWD powoduje, że są one względnie pierwsze.
Przykładowo dla liczb 2 i 8: NWD(2, 8) = 2, więc NWW(2, 8) = 2·8 / 2 = 8. Z kolei dla dwóch liczb, które od razu są liczbami względnie pierwszymi tj. 4 i 11 otrzymujemy, że NWD(4, 11) = 1, więc wtedy wzór upraszcza się do pomnożenia dwóch liczb, więc NWW(4, 11) = 4·11.
Poniższa funkcja NWW przyjmuje, że a jest większą wartością, więc na początku sprawdzana jest poprawność danych wejściowych. Jeśli warunek nie jest prawdziwy to zwrócony zostaje wynik funkcji z zamienionymi argumentami. Dalsza część kodu polega na zwiększaniu wartości tak długo, aż będzie podzielna przez b.
Poniższa funkcja nww() korzysta z funkcji nwd(), które opis implementacji można znaleźć tutaj. Jak widać rozwiązanie jest jednolinijkowe, ale nie oznacza to, że jest szybsze od poprzedniego, ponieważ większość obliczeń jest w funkcji nwd().
W celu wczytania od użytkowników liczb a i b i wypisaniu ich NWW można posłużyć się poniższym fragmentem kodu: