NWD
Kliknij na przycisk "Pokaż".
Algorytm Euklidesa na Wikipedii
Kody źródłowe w różnych językach programowania
Algorytm:
Sprawdźmy: Weźmy dwie liczby 20 i 15 Reszta z dzielenia 20:15 to 5 Bierzemy 15 i 5 Reszta z dzielenia 15:5 to 0. Koniec. NWD to 5.
Weźmy dwie liczby 24 i 16 24:16 -> reszta to 8 16:8 -> reszta to 0 NWD to 8
Sprawdź to zmieniając liczby a i b w kodzie.
W kodzie czekamy na zakończenie pętli gdy reszta będzie równa zero (b=reszta=0). Wykorzystujemy też fakt, że nawet jeśli ustawimy liczby odwrotnie: mniejsza, potem większa to zamienią się za chwilę po prostu miejscami, gdyż np. 15 modulo (%) 20 to 15 a zawsze bierzemy w następnym kroku liczbę PRZEZ KTÓRĄ DZIELIMY (tu: 20) i resztę (tu: 15). Czyli weźmiemy w następnym kroku już nie 15 i 20 tylko 20 i 15.