algorytm Euklidesa

Jeden z najbardziej znanych, a jednocześnie najstarszych algorytmów jest algorytm Euklidesa. Powstał ok. 300 r. p.n.e. Jego autorem jest Euklides. Algorytm ten jest rekurencyjny. Założenia tego algorytmu są proste. Jeśli mamy obliczyć NWD liczb m i n, to:

Najpierw sprawdzamy czy liczba n=0

Jeśli tak jest, to NWD liczb m i n=m

Jeśli tak nie jest, to wprowadzamy rekurencyjnie algorytm dla liczb n oraz (m mod n), czyli liczymy NWD dla liczb (n, (m mod n)).