[PHP] Jak policzyć największy wspólny dzielnik (NWD)?

Chcesz wyliczyć największy wspólny dzielnik dla podanych liczb.

Aby wyliczyć największy wspólny dzielnik wystarczy zastosować w praktyce algorytm Euklidesa, który jest z założenia algorytmem rekurencyjnym, ale nic nie stoi na przeszkodzie aby zamiast rekurencji użyć metody iteracyjnej. Zobacz jak obliczyć największy wspólny dzielnik:

function nwd($a,$b) {

while ($b<>0) {

$c=$a;

$a=$b;

$b=$c%$b;

}

return $a;

}

echo nwd(54,69);

Funkcja nwd() po podaniu dwóch liczb wykonuje algorytm Euklidesa w pętli, wyliczając największy wspólny dzielnik dwóch liczb.

Algorytm jest bardzo prosty. Wystarczy sprawdzić czy liczba b=0. Jeżeli tak, to największym wspólnym podzielnikiem jest liczba a i obliczenia są skończone. Jeżeli nie, wtedy za liczbę a trzeba podstawić liczbę b, a w miejsce liczby b trzeba podstawić wynik (a modulo b) i znowu sprawdzić czy b=0.