Najmniejsza wspólna wielokrotność

Kategoria: Zadania z programowania

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 (instrukcja jak rozkładać na czynniki pierwsze)
  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:

#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;
}

Komentarze

Mateusz

Program obliczający NWW nie działa w sytuacji, gdy użytkownik poda dwie takie same liczby. Zamiast petli do while powinna być pętla while, aby pętla nie była nieskończona.

pani c++

bardzo przydatne, dla młodych adeptów programowania
polecam!

Ocet

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

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *