Algorytm Euklidesa z resztą z dzielenia (modulo)

Algorytm Euklidesa: NWD i NWW - Algorytmy z podstawy programowej (Python)

Gdy jedna liczba jest dużo większa od drugiej, odejmowanie trwa długo: NWD(1000, 7) to ponad sto odejmowań. Wiele odejmowań tej samej liczby to po prostu **reszta z dzielenia**, więc szybsza wersja zamienia parę (a, b) na (b, a % b), aż b stanie się zerem. Wtedy a jest szukanym NWD. ``` a b a % b 48 18 12 18 12 6 12 6 0 6 0 koniec ``` To ta wersja pojawia się na maturze i w zadaniach egzaminacyjnych.

a = 48
b = 18
while b != 0:
    reszta = a % b
    print(a, b, reszta)
    a = b
    b = reszta
print("NWD =", a)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy z podstawy programowej·Zaloguj się, aby zapisać postęp na koncie.