Euklides opracował prosty i efektywny algorytm wyznaczania NWD (największy wspólny dzielnik).
Dla danych dwóch liczb a i b polega on na odejmowaniu od większej mniejszej. Gdy liczby są równe otrzymamy NWD.
max{a,b}:=max{a,b}-min{a,b} gdzie max{a,b}, min{a,b} oznaczają odpowiednio największy i najmniejszą liczbę ze zbioru {a,b}.
Najlepiej zrozumieć to na przykładach:

a b max{a,b}-min{a,b} 24 6 24-6=18 18 6 18-6=12 12 6 12-6=6 6 6 NWP=6

a b max{a,b}-min{a,b} 3 10 10-3=7 3 7 7-3=4 3 4 4-3=1 3 1 3-1=2 2 1 2-1=1 1 1 NWP=1

Schemat blokowy tego algorytmu można przedstawić następująco:

Komentarze