Algorytm Euklaidesa

Algorytm Euklidesa – algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Został opisany przez greckiego matematyka, Euklidesa w jego dziele „Elementy”, w księgach siódmej oraz dziesiątej.

NWD dla liczb 21 i 18

(21,18) - (21-18,21)

(3,18) - (3,18-3)

(3,15) - (3,15-3)

(3,12) - (3,12-3)

(3,9) - (3,9-3)

(3,6) - (3,6-3)

(3,3) - koniec NWD

(21,18)=3