Algorytm Euklidesa

Słownik kwalifikacji INF.04 - Projektowanie, programowanie i testowanie aplikacji

Algorytm Euklidesa służy do obliczania Największego Wspólnego Dzielnika, czyli NWD dwóch liczb naturalnych. NWD to największa liczba, która dzieli obie podane liczby bez reszty.

W pytaniach egzaminacyjnych algorytm Euklidesa często występuje jako schemat blokowy z porównywaniem dwóch zmiennych a i b oraz ich odejmowaniem.

Wersja przez odejmowanie

Dla dodatnich liczb a i b:

  • jeśli a = b, to NWD wynosi a,
  • jeśli a > b, podstaw a := a - b,
  • jeśli b > a, podstaw b := b - a,
  • powtarzaj aż liczby będą równe.

Przykład dla a = 18, b = 12:

18, 12 -> a > b, więc a = 18 - 12 = 6
6, 12 -> b > a, więc b = 12 - 6 = 6
6, 6 -> a = b, więc NWD = 6

Wersja z modulo

Częściej w programowaniu stosuje się szybszą wersję z resztą z dzielenia:

dopóki b != 0:
    r = a mod b
    a = b
    b = r
wynik = a

Na co uważać na egzaminie?

Algorytm Euklidesa nie służy do znajdowania największego elementu tablicy ani liczby pierwszej. Jego podstawowe zastosowanie to obliczanie NWD. NWW można obliczyć pośrednio z użyciem NWD, ale sam algorytm Euklidesa bezpośrednio wyznacza NWD.