Algorytm Euklidesa, wyznaczanie NWD

Algorytm Euklidesa, służy do wyznaczania największego wspólnego dzielnika dowolnie wybranych dwóch liczb naturalnych. Został on stworzony w IV wieku p.n.e. przez Eudoksosa z Knidos.

Pozwala on na wyznaczenie NWD nie rozkładając liczb na czynniki pierwsze. Cały algorytm opiera się na poniższym założeniu:

algorytm-euklidesa

Zasada działania:

  1. Użytkownik musi wprowadzić dwie liczby naturalne, do zmiennych a oraz b;
  2. do zmiennej c przypisujemy resztę z dzielenia a przez b;
  3. zmienną a zastępujemy wartością zmiennej b, a do b przypisujemy wartość c;
  4. jeżeli b = 0 to NWD = a, jeżeli nie przejdź do punktu 2.

Przykładowy program wykorzystujący algorytm Euklidesa (napisany w języku Pascal):

,