Algorytm Euklidesa: jak działa i jak zapisać go w programie

Co robi algorytm i na czym polega jego idea

Największy wspólny dzielnik liczb naturalnych a i b to największa liczba, przez którą dzielą się obie. Dla 48 i 18 dzielnikami wspólnymi są 1, 2, 3 i 6, więc NWD(48, 18) = 6. Szukanie go przez rozkład na czynniki pierwsze lub wypisywanie dzielników działa przy małych liczbach. Algorytm Euklidesa nie wymaga żadnego z tych kroków, bo korzysta z jednej własności:

NWD(a, b) = NWD(b, a mod b), gdzie „a mod b” to reszta z dzielenia a przez b.

Algorytm opisał grecki matematyk Euklides w „Elementach”. Należy do najstarszych algorytmów liczbowych, które nadal się stosuje.

Dlaczego ta własność jest prawdziwa

Niech q będzie ilorazem całkowitym z dzielenia a przez b, a r resztą, czyli a = q · b + r. Rozumowanie ma dwie strony.

1. Każdy wspólny dzielnik liczb a i b dzieli też r, bo r = a − q · b jest różnicą dwóch liczb podzielnych przez ten dzielnik.
2. Każdy wspólny dzielnik liczb b i r dzieli też a, bo a = q · b + r jest sumą dwóch liczb podzielnych przez ten dzielnik.

Pary (a, b) i (b, r) mają więc dokładnie te same wspólne dzielniki, a zatem ten sam największy. Para (b, r) jest „mniejsza”: reszta r jest mniejsza od b. Po skończonej liczbie kroków reszta spada do 0. Wtedy zostaje para (d, 0), a każda liczba dzieli 0, więc największym wspólnym dzielnikiem jest d. To uzasadnia zarówno poprawność, jak i skończoność algorytmu.

Podobnie uzasadnia się odejmowanie: wspólne dzielniki liczb a i b dzielą różnicę a − b, a wspólne dzielniki liczb a − b i b dzielą sumę (a − b) + b = a, więc NWD(a, b) = NWD(a − b, b).

Wersja z odejmowaniem

Starsza, pierwotna postać odejmuje mniejszą liczbę od większej, aż obie będą równe. Wspólna wartość jest NWD.

Pseudokod.

dane: liczby naturalne a, b (obie większe od 0)
dopóki a ≠ b:
    jeśli a > b:
        a := a − b
    w przeciwnym razie:
        b := b − a
wynik: a

Python.

def nwd_odejmowanie(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

print(nwd_odejmowanie(48, 18))  # 6

Przebieg dla a = 48 i b = 18:

Warunek początkowy ma znaczenie: dla b = 0 pętla nigdy by się nie zakończyła, bo odejmowanie zera niczego nie zmienia. Dlatego liczby muszą być dodatnie.

Wadą tej wersji jest duża liczba operacji odejmowania. Dla pary 1000 i 6 potrzeba 168 odejmowań, a dla 1 000 000 i 1 aż 999 999.

Wersja z resztą z dzielenia (modulo)

Kilka odejmowań tej samej liczby z rzędu to właśnie dzielenie z resztą. Operacja „odejmuj b od a, dopóki a ≥ b” kończy się dokładnie na reszcie a mod b. Zastąpienie ciągu odejmowań jednym działaniem modulo daje wersję, którą stosuje się w praktyce.

Pseudokod.

dane: liczby naturalne a, b
dopóki b ≠ 0:
    r := a mod b
    a := b
    b := r
wynik: a

Python.

def nwd_reszta(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(nwd_reszta(1071, 462))  # 21

Zapis a, b = b, a % b oblicza prawą stronę przed przypisaniem, więc nie potrzeba zmiennej pomocniczej r. Przebieg dla a = 1071 i b = 462:

Obie wersje dają ten sam wynik, lecz liczba kroków bardzo się różni:

Liczby kroków w tabeli pochodzą z uruchomienia obu funkcji z licznikiem pętli w Pythonie 3.13.

Wersja rekurencyjna

Własność NWD(a, b) = NWD(b, a mod b) wprost przekłada się na funkcję, która wywołuje samą siebie. Przypadkiem bazowym jest b = 0.

funkcja nwd(a, b):
    jeśli b = 0:
        zwróć a
    zwróć nwd(b, a mod b)

def nwd_rekurencyjnie(a, b):
    if b == 0:
        return a
    return nwd_rekurencyjnie(b, a % b)

print(nwd_rekurencyjnie(48, 18))  # 6

Kolejne wywołania dla 48 i 18: nwd(48, 18), nwd(18, 12), nwd(12, 6), nwd(6, 0), które zwraca 6. Wynik z najgłębszego wywołania przechodzi bez zmian przez wszystkie poprzednie, bo każde zwraca dokładnie to, co jego następca. Liczba wywołań jest taka sama jak liczba obrotów pętli w wersji iteracyjnej, powiększona o ostatnie wywołanie z b = 0. Wersja z pętlą nie zużywa pamięci na stos wywołań, więc przy bardzo długich ciągach reszt jest bezpieczniejsza, ale przy typowych danych różnica nie ma znaczenia.

Przypadki brzegowe

Wersja z odejmowaniem obsługuje tylko liczby dodatnie, więc przy zerach trzeba ją zabezpieczyć warunkiem albo użyć wersji z resztą.

Złożoność: ile kroków potrzeba

Wersja z odejmowaniem może wykonać liczbę kroków porównywalną z samą wartością większej liczby, co pokazuje para 1 000 000 i 1. Wersja z resztą potrzebuje znacznie mniej, bo każde dzielenie z resztą zastępuje wiele odejmowań. Dla niej najgorszym przypadkiem są kolejne liczby Fibonacciego: każdy iloraz wynosi wtedy 1 (poza ostatnim), a reszty maleją możliwie wolno. Pokazuje to tabela z uruchomienia programu:

Tabela pokazuje co drugą parę kolejnych liczb Fibonacciego, więc kroków przybywa w niej po dwa; przy przejściu do następnej pary w ciągu przybywa jeden krok. Liczba kroków rośnie więc wolno wraz z wielkością liczb, a nie z ich wartością. Według Wikipedii Gabriel Lamé udowodnił w 1844 roku, że wersja z resztą nie wymaga więcej dzieleń niż pięciokrotność liczby cyfr mniejszej z liczb (twierdzenie Lamégo), a jego praca jest uważana za pierwszą analizę złożoności obliczeniowej algorytmu. Tabela przedstawia tylko przykłady, a nie dowód.

NWW przez NWD

Najmniejsza wspólna wielokrotność (NWW) dwóch liczb dodatnich jest związana z NWD wzorem: NWW(a, b) = a · b / NWD(a, b). Dla 48 i 18 mamy 48 · 18 = 864, a po podzieleniu przez 6 wychodzi 144.

def nww(a, b):
    return a // nwd_reszta(a, b) * b

print(nww(48, 18))  # 144
print(nww(4, 6))    # 12

Dzielenie wykonuje się przed mnożeniem (a // NWD * b), żeby wartości pośrednie były mniejsze niż iloczyn a · b. W Pythonie liczby całkowite mają nieograniczony rozmiar, ale w językach z ograniczonym typem całkowitym iloczyn dużych liczb mógłby przekroczyć zakres. Wzór dotyczy liczb dodatnich: dla zera NWW przyjmuje się umownie jako 0.

Gotowa funkcja math.gcd i math.lcm

Moduł math ma gotowe funkcje do obu zadań. Dokumentacja Pythona opisuje gcd jako największy wspólny dzielnik argumentów całkowitych, a lcm jako ich najmniejszą wspólną wielokrotność.

import math

print(math.gcd(48, 18))      # 6
print(math.lcm(48, 18))      # 144
print(math.gcd(48, 18, 30))  # 6: wiele argumentów
print(math.gcd(0, 0))        # 0

Według dokumentacji funkcja gcd pojawiła się w wersji 3.5, a obsługę dowolnej liczby argumentów dodano w wersji 3.9, w której pojawiła się też funkcja lcm. Jeśli wszystkie argumenty gcd są zerem, wynik to 0. Na lekcji i na egzaminie piszesz algorytm samodzielnie, ale w programie, który ma tylko działać, lepiej użyć funkcji ze standardowej biblioteki.

Sprawdzenie własnej funkcji

Własną implementację warto porównać z funkcją wzorcową na wielu losowych danych. Poniższy program sprawdza trzy wersje na 10 000 par liczb od 1 do 1000 (odejmowanie wolno działa dla dużych liczb):

import math
import random

random.seed(1)
zgodne = True
for _ in range(10000):
    a = random.randint(1, 1000)
    b = random.randint(1, 1000)
    wzorzec = math.gcd(a, b)
    if not (nwd_odejmowanie(a, b) == nwd_reszta(a, b)
            == nwd_rekurencyjnie(a, b) == wzorzec):
        zgodne = False
print(zgodne)  # True

Najczęstsze błędy

• Brak zabezpieczenia przed zerem w wersji z odejmowaniem. Dla b = 0 pętla jest nieskończona.
• Odwrócona kolejność przypisań. Instrukcja a = b wykonana przed b = a % b niszczy starą wartość a. W Pythonie unika się tego zapisem a, b = b, a % b; w językach bez przypisania krotkowego potrzebna jest zmienna pomocnicza.
• Zły warunek pętli. Wersja z resztą kończy się, gdy b = 0, a wersja z odejmowaniem, gdy a = b. Pomylenie ich daje pętlę nieskończoną albo wynik 0.
• Przeoczone przypadki brzegowe. Sprawdź dane, w których a < b, jedna z liczb jest zerem albo obie są równe.

Zobacz też: Algorytm, Rekurencja, Sito Eratostenesa.

Najczęstsze pytania (FAQ)

Co to jest algorytm Euklidesa?

To algorytm wyznaczania największego wspólnego dzielnika dwóch liczb. Opiera się na zależności NWD(a, b) = NWD(b, a mod b) i kończy się, gdy reszta z dzielenia wynosi 0.

Czym różni się wersja z odejmowaniem od wersji z resztą?

Obie dają ten sam wynik. Wersja z odejmowaniem w każdym kroku odejmuje mniejszą liczbę od większej, a wersja z resztą zastępuje wiele takich odejmowań jednym dzieleniem z resztą. Dla 1000 i 6 to 168 kroków wobec 3.

Czy kolejność liczb ma znaczenie?

Nie. Gdy pierwsza liczba jest mniejsza od drugiej, pierwszy krok wersji z resztą zamienia je miejscami, bo a % b = a dla a < b.

Jak obliczyć NWW za pomocą algorytmu Euklidesa?

Oblicz NWD(a, b), a następnie NWW(a, b) = a / NWD(a, b) · b. Dla 48 i 18 daje to 48 / 6 · 18 = 144.

Czy algorytm Euklidesa działa dla trzech liczb?

Tak. NWD trzech liczb to NWD(NWD(a, b), c), czyli wynik dla pary użyty jako pierwszy argument kolejnego wywołania. Funkcja math.gcd przyjmuje wiele argumentów od Pythona 3.9.

Czy w Pythonie trzeba pisać własną funkcję NWD?

Nie, gotowa jest math.gcd. Własną funkcję pisze się, by ćwiczyć algorytmikę, i taka umiejętność bywa sprawdzana w zadaniach z pisania algorytmów.

Dlaczego algorytm zawsze się kończy?

Reszta z dzielenia przez b jest zawsze mniejsza od b, więc ciąg b maleje i nie może maleć w nieskończoność wśród liczb całkowitych nieujemnych. W pewnym momencie reszta wynosi 0.