Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dwóch liczb całkowitych. Największy wspólny dzielnik dwóch liczb a i b, to taka liczba, która dzieli te liczby bez reszty i jest ona możliwie największa. Można go zastosować do skracania ułamków lub wyznaczenia najmniejszej wspólnej wielokrotności NWW.
Opis algorytmu Euklidesa
Załóżmy, że wyznaczamy NWD dwóch liczb naturalnych a i b. W każdym przejściu pętli wykonujemy dwie operacje
Gdzie mod – reszta z dzielenia całkowitego
Czynności te powtarzamy do momentu, gdy zmienna b osiągnie wartość zero. Zmienna a będzie przechowywać wtedy największy wspólny dzielnik liczb podanych na wejściu. Przeanalizujmy przykłady:
Policzmy:
Dla liczb 28 i 24:
