1 – PYTHON – ALGORYTMY. Algorytm Euklidesa

Algorytm Euklidesa to sposób na znalezienie największego wspólnego dzielnika (NWD) dwóch liczb, w wersji z odejmowaniem działa on tak:

  1. Weź dwie liczby naturalne a i b, gdzie a > 0 i b > 0.
  2. Sprawdź, czy a = b. Jeśli tak, to a jest największym wspólnym dzielnikiem (NWD).
  3. Jeśli a > b, odejmij b od a (a = a – b).
  4. Jeśli b > a, odejmij a od b (b = b – a).
  5. Powtarzaj kroki 2-4, aż a = b.
  6. Zwróć wartość a (NWD).

Poniżej przedstawiona jest realizacja algorytmu w programie Scratch oraz Python.

a = 5
b = 21

while a != b:
  if a > b:
    a = a - b
  else:
    b = b - a
    
print(a)