Największy wspólny dzielnik
Podobnie jak wyznaczanie liczb pierwszych, problem znajdowania największego
wspólnego dzielnika (NWD) dwóch liczb naturalnych ma klasyczne i zapewne
wszystkim Czytelnikom znane rozwiązanie. Mowa oczywiście o algorytmie
Euklidesa, jednym z najstarszych do dziś używanych algorytmów. Jest to
rozwiązanie bardzo proste w implementacji, a w wersji z dzieleniem – efektywne:
pozwala wyznaczyć NWD dwóch liczb nie większych niż
w czasie
W pewnych przypadkach istnieją jednak rozwiązania asymptotycznie
szybsze.