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 - q
krok 2. liczbę a zastąp liczbą b, liczbę b liczbą q
krok 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ż:
- Dzielenie z resztą
- Generator liczb losowych
- Kalkulator binarny
- Kalkulator funkcji kwadratowej
- Kalkulator logarytmów
- Kalkulator macierzy
- Kalkulator modulo
- Kalkulator naukowy online
- Kalkulator pierwiastków
- Kalkulator potęg
- Kalkulator procentowy
- Kalkulator ułamków
- Najmniejsza wspólna wielokrotność (NWW)
- Objętość i pole walca - kalkulator
- Średnia ważona