Algorytm Euklidesa (NWD i NWW)

Algorytm Euklidesa to jeden z najstarszych i najbardziej eleganckich algorytmów na świecie. Służy do wyznaczania Największego Wspólnego Dzielnika (NWD) dwóch liczb, czyli największej liczby całkowitej, która dzieli obie te liczby bez reszty.

Na maturze jest to absolutny fundament – pojawia się w zadaniach z ułamkami (do ich skracania) oraz w zaawansowanej kryptografii (np. algorytmie RSA).

Wersja klasyczna vs Wersja optymalna

Istnieją dwie główne wersje tego algorytmu:

1. Z odejmowaniem (Klasyczna): Polega na ciągłym odejmowaniu mniejszej liczby od większej, dopóki obie nie staną się równe. Niestety, jeśli podamy bardzo zróżnicowane liczby (np. 1 000 000 i 1), komputer będzie musiał wykonać aż milion operacji odejmowania!
2. Z resztą z dzielenia (Optymalna - Modulo): To tzw. "wersja na sterydach". Zamiast odejmować, wyliczamy z obu liczb resztę z dzielenia (operator %), a następnie "przesuwamy" wartości w pętli. Ten sposób znajdzie NWD dla gigantycznych liczb w ułamek sekundy (w max. kilkunastu krokach).

Na egzaminie zawsze używaj wersji z modulo!

Zrozumienie kodu krok po kroku

Oto algorytm w swojej najpiękniejszej formie wykorzystujący resztę z dzielenia (modulo).

[!TIP] Zauważ, że nie musimy się martwić, czy na początku a jest większe od b. Jeśli a < b, to w pierwszej iteracji pętli z automatu liczby zamienią się miejscami!

Python

def nwd(a, b):
    # Dopóki b nie stanie się zerem, wykonujemy operacje
    while b != 0:
        # Krok 1: Wyliczamy resztę z dzielenia a przez b
        reszta = a % b
        
        # Krok 2: Przesuwamy liczby. 'a' przyjmuje wartość 'b'
        a = b
        
        # Krok 3: 'b' przyjmuje wartość wyliczonej reszty
        b = reszta
        
    # Kiedy pętla się zakończy (bo b = 0), wynikiem NWD jest a
    return a

# Testowanie:
wynik = nwd(1989, 867)
print(f"NWD: {wynik}")

C++

#include <iostream>
using namespace std;

int nwd(int a, int b) {
    // Dopóki b nie stanie się zerem, wykonujemy operacje
    while (b != 0) {
        // Krok 1: Wyliczamy resztę z dzielenia a przez b
        int reszta = a % b;
        
        // Krok 2: Przesuwamy liczby. 'a' przyjmuje wartość 'b'
        a = b;
        
        // Krok 3: 'b' przyjmuje wartość wyliczonej reszty
        b = reszta;
    }
    // Kiedy pętla się zakończy (bo b = 0), wynikiem NWD jest a
    return a;
}

int main() {
    int wynik = nwd(1989, 867);
    cout << "NWD: " << wynik << endl;
    return 0;
}

Najmniejsza Wspólna Wielokrotność (NWW)

Skoro znasz już NWD, obliczenie NWW (Najmniejszej Wspólnej Wielokrotności) to bułka z masłem. Opiera się na prostej matematycznej zależności: mnożysz obie liczby przez siebie i dzielisz wynik przez ich NWD.

Wzór: NWW = (a * b) / NWD(a, b)

Python

def nww(a, b):
    # Dzielenie całkowite // aby pozbyć się kropki na końcu (float)
    return (a * b) // nwd(a, b)

C++

int nww(int a, int b) {
    return (a * b) / nwd(a, b);
}

[!WARNING] Pamiętaj, że dla bardzo dużych liczb ich iloczyn (a * b) może przekroczyć zakres standardowych zmiennych typu całkowitego w C++ (zjawisko integer overflow). Z tego powodu dobrym nawykiem jest zapisanie wzoru jako: a / NWD(a, b) * b. W ten sposób najpierw zmniejszasz wartość przez dzielenie, a dopiero potem mnożysz. W języku Python ten problem nie występuje.