Największy wspólny dzielnik

Kategoria: Zadania z programowania

Największy wspólny dzielnik kilku liczb to największa liczba naturalna dzieląca wszystkie z tych liczb. Obliczanie NWD dla małych liczb można wykonać ręcznie w pamięci, jednak przy większych liczbach dobrze posłużyć się pewnymi algorytmami (np. algorytmem Euklidesa).

Największy wspólny dzielnik

W celu obliczenia największego wspólnego dzielnika należy przeprowadzić następujące kroki:

  1. Rozłożyć liczby na iloczyn czynników pierwszych (instrukcja jak rozkładać na czynniki pierwsze)
  2. Wymnożyć wspólne czynniki pierwsze, które powtarzają się zarówno dla jednej i drugiej liczby.

Przykładowo, obliczmy NWD dla liczb 56 i 100:

56=2*2*2*7\\
100=2*2*5*5\\

Jedyne wspólne czynniki pierwsze to 2 i 2. W takim razie:

NWD(56,100)=2*2=4\\

Program w C++ (iteracyjny)

Przykładowy program, pozwalający obliczyć największy wspólny dzielnik dwóch liczb, za pomocą algorytmu Euklidesa.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int a, b;
    cout << "Podaj pierwsza liczbe: ";
    cin >> a;
    cout << "Podaj druga liczbe: ";
    cin >> b;

    do
    {
        if(a > b) {
           a = a - b;
        } else {
            b = b - a;
        }
    }
    while(a != b);

    cout << "Najwiekszy wspolny dzielnik: " << a << endl;

    system("PAUSE");

    return 0;
}

Komentarze

Bartosz

Algorytm zawiera drobną nieścisłość. W przypadku podania a=b, czyli dwóch takich samych liczb, algorytm się zapętla i nie zwraca nic, a powinien zwrócić a (lub b, b to to samo). Rozwiązaniem jest przesunięcię while na górę, albo zastąpienie else if (b>a).
Pozdrawiam

W2

Yeeeeeey! Nareszcie mam 2 z informatysi.

Mirek_Szyperek

Bardzo fajny blog! Często udostępniam go moim podopiecznym w celu polepszenia ich umiejętności programistycznych.
Pozdrawiam serdecznie wszystkich bloggersów!
🙂

MAX

Cześć, nie wiem czy jest to błąd strony czy czegoś innego, ale nie widzę przykładowych kodów, które wstawiłeś jako rozwiązanie, mam jedynie „Przykładowy program, pozwalający obliczyć największy wspólny dzielnik dwóch liczb, za pomocą algorytmu Euklidesa.” No i od razu po tym jest okienko z napisem „Jaka jest Twoja opinia?”… Da się jakoś rozwiązać ten problem?

//Karol: Cześć, rzeczywiście jest błąd. Naprawię go dziś lub jutro, wtedy kody znów będą widoczne

jakub

Faktycznie Jerymme, dzięki. Dodałem if-a if(a==b)cout a; I pomogło, to jednak o ten warunek chodziło w SPOJ 🙂 Nieważne :p

Szymon

wystarczy dać ((a>b)&&(a!=b))

W.

Jeeej, ocena z informatysi uratowana! Dziękuję 😉

Jerryme

#include
#include

using namespace std;

int main()
{
int a, b;
cout <> a;
cout <> b;

while(a!=b)
{
if(a>b) a=a-b;
else b=b-a;
}

cout << "Najwiekszy wspolny dzielnik: " << a << endl;

system("PAUSE");

return 0;
}

Jeśli liczby były by takie same nie zadziała. wiem ze sprawdzanie NWD dla 2 takich samych liczb jest bez sensu ale mogą się przyczepić

Oskar

Przydatny, jak wszystkie. :))

Dodaj komentarz

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