Największy wspólny dzielnik (NWD) obliczysz, gdy w specjalnie do tego przeznaczone rubryki wpiszesz dwie liczby całkowite.
A poniżej kalkulatora możesz przeczytać także o tym, jakie algorytmy wykorzystywane są do obliczenia największego wspólnego dzielnika.
Największy wspólny dzielnik (NWD) - definicja
Największy wspólny dzielnik (w skrócie NWD), dla dwóch liczb całkowitych, jest to największa liczba naturalna dzieląca każdą z nich.
Gdy mamy dwie liczby a i b to największy wspólny dzielnik zapisuje się jako NWD(a, b).
Przykład: NWD(18, 12) = 6.
Algorytm Euklidesa
Euklides to grecki matematyk, który w swoim dziele Elementy opisał algorytm do wyznaczania największego wspólnego dzielnika. Został on opisany około 300 lat p.n.e. i jest on jednym z najstarszych, wciąż używanych algorytmów numerycznych.
Istnieją dwie wersje Algorytm Euklidesa: wykorzystującą odejmowanie i wykorzystującą funkcję modulo
- Algorytm wykorzystujący funkcję modulo
krok 1. dla liczb a i b oblicz resztę z dzielenia - qkrok 2. liczbę a zastąp liczbą b, liczbę b liczbą qkrok 3. jeśli b wynosi 0, to a jesz szukaną wartością, w przeciwnym przypadku przejdź do kroku 1
Zastosowanie Największego Wspólnego Dzielnika
Największy Wspólny Dzielnik potrzebny jest do obliczania Najmniejszej Wspólnej Wielokrotności (NWW).
zobacz również: