Algorytm Euklidesa

Algorytm Euklidesa (metoda kolejnych dzielen) to algorytm znajdowania 
najwiekszego wspolnego dzielnika (NWD) dwoch roznych liczb naturalnych. 
Nie wymaga rozkadania liczb na czynniki pierwsze. Pochodzi z czwartego wieku
przed nasza era.

   1. dane sa dwie liczby naturalne dodatnie a i b,
       szukamy ich NWD

   2. oblicz c jako reszte z dzielenia a przez b

   3. zastap a przez b, zas b przez c

   4. jezeli b = 0, to szukane NWD = a, w przeciwnym wypadku przejdz do 2



PRZYKLAD:


NWD liczb 1001 i 42 wynosi 7, zas obliczenia przebiegaja nastepujaco:

a 	   b 	   c
1001 	42 	35
42 	35 	7
35 	7 	0
7 	0 	-