Python: NWD - Największy wspólny dzielnik

Definicja

Największy wspólny dzielnik (NWD) dla dwóch liczb jest to największa liczba naturalna, która dzieli każdą z tych liczb bez reszty.

Na przykład dla 16 i 24, największą liczbą naturalną która dzieli te dwie liczby bez reszty jest 8.

Dla liczb 3 i 9 jest to 3.

Natomiast dla liczb 3 i 7 NWD będzie wynosić 1.

NWD rekurencyjnie

Oto najbardziej skrócona wersja rekurencyjnego algorytmu NWD, idealna do zapamiętania:

def nwd(a, b): return nwd(b, a%b) if b else a

Dla jasności, powyższa linijka po rozpisaniu wygląda następująco:

def nwd(a, b):
    if b > 0:
        return nwd(b, a%b)
    else:
        return a

W zasadzie to else możemy, a wręcz powinniśmy w tej sytuacji pominąć:

def nwd(a, b):
    if b > 0:
        return nwd(b, a%b)
    return a

NWD iteracyjnie

Najkrótsza wersja iteracyjnego NWD:

def nwd_i(a, b):
    while b:
        a, b = b, a%b
    return a

Pętla while b: wykonuje się tak długo, jak b jest większe od 0.

W innych językach programowania niemożliwa jest zamiana wartości dwóch zmiennych jednocześnie bez wykorzystywania zmiennej pomocniczej lub funkcji swap, jednak w Pythonie jest to możliwe używając zapisu a, b = b, a%b.

A tak wygląda ten sam algorytm przy wykorzystaniu zmiennej pomocniczej (temp):

def nwd_i(a, b):
    while b:
        temp = a
        a = b
        b = temp%b
    return a