Największy wspólny dzielnik C++

Ostatania modyfikacja: 22 kwietnia 2019, kategoria: Matura z informatyki

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
  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.

Użytkownik Oskar napisał:

21 maja 2013


Przydatny, jak wszystkie. :))

Użytkownik Jerryme napisał:

12 maja 2015


#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ć

Użytkownik W. napisał:

04 czerwca 2016


Jeeej, ocena z informatysi uratowana! Dziękuję ;)

Użytkownik Szymon napisał:

15 czerwca 2016


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

Użytkownik jakub napisał:

21 lutego 2019


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

Zachęcam Cię do zostawienia komentarza!

Ilość znaków: 0