Algorytm Euklidesa

Algorytm Euklidesa – algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Jest to jeden z najstarszych algorytmów. Opiera się on na spostrzeżeniu, że jeśli od większej liczby odejmiesz mniejszą, to mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego odejmowania otrzymasz parę równych liczb, oznacza to, że znalazłeś nwd.