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:

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):

program NWD;
USES crt;
VAR
    a,b,c:integer;
BEGIN
    clrscr;
    writeln('Podaj dwie liczby naturalne:');
    readln(a);
    repeat
         writeln('Druga liczba musi być różna od O:');
         readln(b);
    until b <> 0;

    {obliczamy NWD}

    repeat
         c := a mod b;
         a := b;
         b := c;
    until b = 0;
    
    {wyświetlamy wynik}
    writeln('NWD = ', a);
    repeat until keypressed;
end.

Algorytm Euklidesa, wyznaczanie NWD