Największy wspólny dzielnik NWD w Pythonie - krok po kroku

Największy wspólny dzielnik dwóch liczb to po prostu największa liczba, przez którą obie da się podzielić bez reszty. Jeśli mamy na przykład 18 i 48, wspólnymi dzielnikami są 1, 2, 3 i 6, a największym z nich jest 6. W Pythonie NWD można policzyć na kilka sposobów: sprawdzając kolejne dzielniki, korzystając z algorytmu Euklidesa albo używając gotowej funkcji math.gcd(). Dla osoby uczącej się programowania najbardziej wartościowy jest algorytm Euklidesa, bo dobrze pokazuje, jak prosty pomysł matematyczny można zamienić na krótki i bardzo szybki program.

Co to jest największy wspólny dzielnik?

Największy wspólny dzielnik, w skrócie NWD, to największa liczba całkowita, która dzieli dwie liczby bez pozostawienia reszty.

Nie trzeba od razu podchodzić do tego jak do trudnego zagadnienia matematycznego. Weźmy liczby 12 i 18. Liczbę 12 można podzielić bez reszty między innymi przez 1, 2, 3, 4, 6 i 12. Liczba 18 dzieli się natomiast przez 1, 2, 3, 6, 9 i 18.

W obu zestawach występują 1, 2, 3 i 6. Największą z tych liczb jest 6, więc:

NWD(12, 18) = 6

I właściwie na tym polega całe zagadnienie. Trudniejsza część zaczyna się dopiero wtedy, gdy chcemy znaleźć NWD szybko, szczególnie dla dużych liczb. Sprawdzanie wszystkich możliwych dzielników jest łatwe do zrozumienia, ale istnieje znacznie sprytniejszy sposób.

NWD na prostym przykładzie

Zanim przejdziemy do kodu w Pythonie, policzmy NWD zwykłą metodą dla liczb 48 i 18.

Dzielniki liczby 48 to między innymi:

1, 2, 3, 4, 6, 8, 12, 16, 24, 48

Dzielniki liczby 18:

1, 2, 3, 6, 9, 18

Wspólne dzielniki to:

1, 2, 3 i 6

Największy z nich to 6, dlatego:

NWD(48, 18) = 6

Dla takich liczb można to bez problemu policzyć na kartce. Gdy jednak pojawią się liczby takie jak 123456 i 7890, wypisywanie wszystkich dzielników szybko przestaje być przyjemne. Tutaj przydaje się algorytm.

Prosta metoda obliczania NWD w Pythonie

Na początek można napisać program dokładnie tak, jak policzylibyśmy NWD ręcznie. Sprawdzamy kolejne liczby i zapamiętujemy największą, która dzieli obie liczby bez reszty.

def nwd(a, b):
    wynik = 1

    for i in range(1, min(a, b) + 1):
        if a % i == 0 and b % i == 0:
            wynik = i

    return wynik

print(nwd(48, 18))

Program wyświetli:

6

Pętla zaczyna od 1 i dochodzi do mniejszej z dwóch liczb. Dalsze sprawdzanie nie miałoby sensu, ponieważ wspólny dzielnik nie może być większy od mniejszej liczby.

Warunek:

a % i == 0 and b % i == 0

sprawdza, czy zarówno a, jak i b dzielą się przez i bez reszty. Za każdym razem, gdy znajdziemy taki dzielnik, zapisujemy go w zmiennej wynik. Ponieważ przechodzimy przez liczby rosnąco, na końcu zostaje największy wspólny dzielnik.

Ta wersja ma sporą zaletę: bardzo łatwo zrozumieć, co robi. Nie jest jednak szczególnie szybka. Przy większych liczbach wykonuje wiele niepotrzebnych sprawdzeń.

Algorytm Euklidesa - szybszy sposób obliczania NWD

Algorytm Euklidesa podchodzi do problemu zupełnie inaczej. Nie szuka kolejnych dzielników. Wykorzystuje resztę z dzielenia dwóch liczb.

Pomysł jest prosty: dzielimy większą liczbę przez mniejszą i zapamiętujemy resztę. Następnie bierzemy poprzednią mniejszą liczbę i dzielimy ją przez otrzymaną resztę. Powtarzamy to do momentu, gdy reszta wyniesie 0.

Ostatnia liczba, przez którą dzieliliśmy przed otrzymaniem zera, jest największym wspólnym dzielnikiem.

Brzmi trochę bardziej matematycznie niż zwykłe sprawdzanie dzielników, ale na konkretnym przykładzie mechanizm robi się bardzo czytelny.

Algorytm Euklidesa na przykładzie 48 i 18

Policzmy ponownie NWD(48, 18), tym razem metodą Euklidesa.

Najpierw dzielimy 48 przez 18 i interesuje nas reszta:

48 % 18 = 12

Teraz zamiast liczb 48 i 18 bierzemy 18 oraz otrzymaną resztę 12:

18 % 12 = 6

Powtarzamy operację jeszcze raz:

12 % 6 = 0

Otrzymaliśmy resztę 0. Ostatnią niezerową liczbą używaną jako dzielnik było 6, dlatego:

NWD(48, 18) = 6

W porównaniu ze sprawdzaniem wszystkich dzielników wykonaliśmy tylko trzy działania. Przy większych liczbach różnica robi się jeszcze bardziej widoczna.

NWD w Pythonie za pomocą algorytmu Euklidesa

Algorytm Euklidesa można w Pythonie zapisać bardzo krótko:

def nwd(a, b):
    while b != 0:
        reszta = a % b
        a = b
        b = reszta

    return a

print(nwd(48, 18))

Wynik:

6

Prześledźmy działanie programu. Na początku:

a = 48
b = 18

Pierwsze przejście pętli daje:

reszta = 48 % 18
reszta = 12

a = 18
b = 12

Drugie:

reszta = 18 % 12
reszta = 6

a = 12
b = 6

Trzecie:

reszta = 12 % 6
reszta = 0

a = 6
b = 0

Warunek while b != 0 przestaje być spełniony. Funkcja zwraca więc wartość a, czyli 6.

Ten sam zapis można dodatkowo skrócić, wykorzystując charakterystyczną dla Pythona możliwość jednoczesnego przypisania dwóch wartości:

def nwd(a, b):
    while b:
        a, b = b, a % b

    return a

print(nwd(48, 18))

Działanie jest dokładnie takie samo. Druga wersja wygląda elegancko i jest często spotykana w Pythonie, ale osoba dopiero ucząca się algorytmów może łatwiej zrozumieć pierwszą wersję z osobną zmienną reszta.

Rekurencyjna wersja algorytmu Euklidesa

Algorytm Euklidesa bardzo dobrze nadaje się również do pokazania rekurencji. Zamiast wykonywać pętlę, funkcja może wywoływać samą siebie dla kolejnych par liczb.

def nwd(a, b):
    if b == 0:
        return a

    return nwd(b, a % b)

print(nwd(48, 18))

Ponownie otrzymamy:

6

Kolejne wywołania funkcji można zapisać tak:

nwd(48, 18)
nwd(18, 12)
nwd(12, 6)
nwd(6, 0)

Gdy druga liczba osiągnie 0, funkcja zwraca pierwszą. Potem wynik wraca przez kolejne wywołania aż do miejsca, z którego rozpoczęliśmy obliczenia.

Rekurencyjna wersja jest bardzo krótka i dobrze pokazuje matematyczną naturę algorytmu Euklidesa. Do prostego programu równie dobrze można jednak użyć wersji z pętlą while, która dla początkujących jest często łatwiejsza do prześledzenia.

NWD w Pythonie z math.gcd()

Jeżeli nie ćwiczymy algorytmów i chcemy po prostu obliczyć największy wspólny dzielnik w prawdziwym programie, Python ma już gotowe rozwiązanie.

Funkcja gcd() znajduje się w module math:

import math

wynik = math.gcd(48, 18)

print(wynik)

Program zwróci:

6

Można również zaimportować samą funkcję:

from math import gcd

print(gcd(48, 18))

Jeżeli celem zadania jest napisanie algorytmu Euklidesa, użycie math.gcd() oczywiście omija całą część algorytmiczną. Przy normalnym tworzeniu programu nie ma jednak powodu pisać własnej funkcji za każdym razem, jeśli standardowa biblioteka Pythona ma już gotowe rozwiązanie.

Która metoda obliczania NWD jest najlepsza?

Wszystkie pokazane sposoby prowadzą do tego samego wyniku, ale służą trochę innym celom.

Jeśli dopiero zaczynasz, najpierw dobrze zrozumieć zwykłe sprawdzanie dzielników. Potem algorytm Euklidesa staje się znacznie bardziej intuicyjny, bo widać, jaki problem właściwie rozwiązuje.

NWD dla zera i liczb ujemnych

Podczas typowych ćwiczeń najczęściej dostajemy dwie dodatnie liczby całkowite. W prawdziwym programie dane wejściowe nie zawsze są jednak tak wygodne.

Dla zera obowiązuje prosta zależność:

NWD(15, 0) = 15
NWD(0, 8) = 8

Algorytm Euklidesa radzi sobie z taką sytuacją naturalnie. Jeśli druga liczba od początku wynosi 0, pętla nie zostanie wykonana i funkcja od razu zwróci pierwszą wartość.

Przy liczbach ujemnych najlepiej sprowadzić dane do wartości bezwzględnych:

def nwd(a, b):
    a = abs(a)
    b = abs(b)

    while b:
        a, b = b, a % b

    return a

print(nwd(-48, 18))

Wynikiem nadal będzie:

6

Gotowe math.gcd() również zwraca nieujemny największy wspólny dzielnik.

Złożoność algorytmu Euklidesa

Największą przewagą algorytmu Euklidesa nie jest to, że jego kod zajmuje kilka linii. Ważniejsze jest to, jak mało operacji potrzebuje do znalezienia wyniku.

Przy metodzie polegającej na sprawdzaniu wszystkich możliwych dzielników możemy wykonać bardzo dużo testów. Dla małych liczb nie ma to większego znaczenia, ale przy dużych wartości szybko zaczyna być niepotrzebnym obciążeniem.

Algorytm Euklidesa zmniejsza problem po każdym wykonaniu operacji modulo. Liczby szybko stają się coraz mniejsze, dlatego liczba potrzebnych kroków rośnie znacznie wolniej.

Jego złożoność czasową najczęściej zapisuje się jako O(log n), co sprawia, że dobrze radzi sobie nawet z dużymi liczbami.

Do czego przydaje się NWD?

NWD nie jest wyłącznie szkolnym zadaniem do przećwiczenia pętli while. Najprostsze zastosowanie to skracanie ułamków.

Mamy na przykład ułamek:

18 / 48

Wiemy już, że:

NWD(18, 48) = 6

Dzielimy więc licznik i mianownik przez 6:

18 / 6 = 3
48 / 6 = 8

Otrzymujemy:

3 / 8

Największy wspólny dzielnik pojawia się też w zadaniach związanych z teorią liczb, kryptografią, obliczaniem najmniejszej wspólnej wielokrotności czy różnego rodzaju problemami algorytmicznymi. Dla osoby uczącej się Pythona jest dodatkowo dobrym przykładem wykorzystania operatora modulo i pętli.

FAQ - NWD w Pythonie