Određivanje NZD i NZS pomoću Euklidovog algoritma

Euklidov algoritam je dobio naziv po grčkom matematičaru Euklidu i koristi se za efikasno određivanje najvećeg zajedničkog delioca (NZD), a preko njega i najmanjeg zajedničkog sadržaoca (NZS) dva ili više celih brojeva.

To je jedan od najstarijih poznatih algoritama. Opisan je u Euklidovim „Elementima” pre više od 2000 godina, a njegova osnovna ideja ostala je ista do danas. U literaturi na engleskom NZD se označava kao GCD (greatest common divisor), a NZS kao LCM (least common multiple).

Zašto je to važno?

• Matematika: skraćivanje razlomaka, problemi deljivosti i rešavanje Diofantovih jednačina pomoću proširenog Euklidovog algoritma.
• Programiranje: jedan od osnovnih algoritama na takmičenjima i odličan primer kako se problem svodi na manji problem istog oblika.
• Kriptografija: prošireni Euklidov algoritam koristi se za računanje modularnog inverza, na primer pri generisanju ključeva u RSA algoritmu.

---

Određivanje najvećeg zajedničkog delioca (NZD)

Određivanje NZD-a dva broja A i B zasniva se na sledećoj činjenici:

Ako je p količnik, a q ostatak deljenja, važi:

A = p · B + q

Pošto su A i p·B deljivi sa d, deljiv je i q = A − p·B. Zato je NZD(A, B) = NZD(B, q): problem smo sveli na manje brojeve.

Primer za brojeve A = 48 i B = 28:

Na slici pod a) prikazan je klasičan način određivanja NZD-a, koji je u ovom slučaju 4. Na slici pod b) vidi se da je NZD sadržan i u brojevima 48 i 28, ali i u ostatku njihovog deljenja:

48 = 1 · 28 + 20

Ako sada tražimo NZD za 28 i 20, dobićemo isti rezultat. Postupak ponavljamo: prethodni delilac postaje deljenik, a ostatak postaje novi delilac, sve dok ostatak ne postane nula (slika pod c):

48 = 1 · 28 + 20
28 = 1 · 20 + 8
20 = 2 · 8  + 4
 8 = 2 · 4  + 0   →  NZD(48, 28) = 4

Traženi NZD je poslednji delilac, odnosno poslednji ostatak različit od nule. Ovaj postupak je poznat kao Euklidov algoritam.

Primer sa većim brojevima

Algoritam je brz i za velike brojeve. Za A = 987654 i B = 123456 potrebna su samo dva koraka:

987654 = 8 · 123456 + 6
123456 = 20576 · 6 + 0   →  NZD(987654, 123456) = 6

Broj koraka Euklidovog algoritma raste srazmerno broju cifara manjeg broja, odnosno složenost je O(log min(A, B)).

---

NZD — iterativni algoritam

Program učitava dva cela broja i određuje njihov NZD. Sa a je označen veći, a sa b manji od ta dva broja.

#include <iostream>
using namespace std;

int main()
{
    int x, y, a, b, NZD, temp;
    cin >> x >> y;

    // a - veći, b - manji od dva učitana broja
    a = (x > y) ? x : y;
    b = (x < y) ? x : y;

    // Ponavljamo deljenje dok ostatak ne postane 0:
    // novi deljenik je stari delilac, a novi delilac je ostatak.
    while (b != 0)
    {
        temp = a;
        a = b;
        b = temp % b;
    }

    // Kada ostatak postane 0, u a se nalazi poslednji delilac,
    // a to je traženi NZD.
    NZD = a;
    cout << NZD << endl;

    return 0;
}

Postupak traženja ostatka deljenja ponavlja se dok je ostatak različit od nule. Kada se petlja završi, u promenljivoj a nalazi se poslednji delilac, a to je traženi NZD. Zapravo, nije ni potrebno unapred odrediti veći broj: ako je a < b, prvi korak petlje sam zameni njihova mesta.

Više o petljama pročitajte na strani Petlje u programskom jeziku C/C++.

---

NZD — rekurzivni algoritam

Umesto iterativno, kroz while petlju, problem se može rešiti i rekurzivno:

#include <iostream>
using namespace std;

// Rekurzivno određivanje NZD-a; pretpostavka je da je a >= b > 0
int NZDRek(int a, int b)
{
    int r = a % b;          // ostatak deljenja
    if (r == 0)
        return b;           // poslednji delilac je NZD
    else
        return NZDRek(b, r); // isti postupak za delilac i ostatak
}

int main()
{
    int a, b, x;
    cin >> a >> b;

    // Funkciji prvo šaljemo veći broj
    if (a > b)
        x = NZDRek(a, b);
    else
        x = NZDRek(b, a);

    cout << x << endl;

    return 0;
}

Funkcija NZDRek prima dva parametra, tako da je prvi veći od drugog. Ako je ostatak deljenja r jednak nuli, vraća se drugi broj, odnosno delilac. Ako nije, funkcija poziva samu sebe sa novim parametrima: prvi je prethodni delilac, a drugi ostatak deljenja.

Više o funkcijama pročitajte na strani Funkcije u C/C++.

---

Određivanje najmanjeg zajedničkog sadržaoca (NZS)

NZS se određuje tako što se prvo odredi NZD, a zatim se koristi veza:

NZS(a, b) · NZD(a, b) = a · b    →    NZS(a, b) = a / NZD(a, b) · b

Za brojeve 48 i 28: NZS = 48 / 4 · 28 = 12 · 28 = 336.

#include <iostream>
using namespace std;

// NZD pomoću Euklidovog algoritma
long long NZD(long long a, long long b)
{
    while (b != 0)
    {
        long long ostatak = a % b;
        a = b;
        b = ostatak;
    }
    return a;
}

int main()
{
    long long a, b;
    cin >> a >> b;

    long long d = NZD(a, b);

    // NZS(a, b) * NZD(a, b) = a * b, pa je NZS = a * b / NZD.
    // Prvo delimo, pa tek onda množimo, da bi međurezultat
    // bio manji i da ne bi došlo do prekoračenja opsega.
    long long nzs = a / d * b;

    cout << "NZD = " << d << endl;
    cout << "NZS = " << nzs << endl;

    return 0;
}

---

Prošireni Euklidov algoritam

Prošireni Euklidov algoritam, pored NZD-a, pronalazi i cele brojeve x i y za koje važi:

a · x + b · y = NZD(a, b)

Zato se koristi za rešavanje linearnih Diofantovih jednačina (jednačina čija se rešenja traže u celim brojevima) i u modularnoj aritmetici.

Primene

• Kriptografija: računanje modularnog inverza u algoritmu RSA.
• Teorija brojeva: rešavanje linearnih kongruencija.
• Takmičenja: zadaci u kojima treba izraziti broj kao kombinaciju dve date vrednosti.

Modularni inverz

Da bi se izračunao inverz broja a po modulu m, prošireni algoritam pronalazi x i y takve da je a·x + m·y = 1. Tada je x (po modulu m) traženi inverz. Inverz postoji samo ako je NZD(a, m) = 1.

Implementacija (rekurzivna, C++17)

#include <iostream>
#include <tuple>

// Prošireni Euklidov algoritam:
// vraća (NZD, x, y) tako da važi a*x + b*y = NZD(a, b)
std::tuple<int, int, int> extended_gcd(int a, int b) {
    if (b == 0) {
        // NZD(a, 0) = a, a važi a*1 + 0*0 = a
        return {a, 1, 0};
    }

    int gcd, x1, y1;
    // Rešavamo isti problem za (b, a % b)
    std::tie(gcd, x1, y1) = extended_gcd(b, a % b);

    // Iz b*x1 + (a % b)*y1 = gcd i a % b = a - (a / b)*b dobijamo:
    int x = y1;
    int y = x1 - (a / b) * y1;

    return {gcd, x, y};
}

// Testiranje funkcije
int main() {
    int a = 48, b = 18;
    int gcd, x, y;

    std::tie(gcd, x, y) = extended_gcd(a, b);

    std::cout << "NZD: " << gcd << ", x: " << x << ", y: " << y << std::endl;

    return 0;
}

Objašnjenje

1. Ulazni parametri: funkcija prima dva cela broja a i b.
2. Bazni slučaj: kada je b = 0, NZD je a, a koeficijenti su x = 1, y = 0.
3. Rekurzivni poziv: funkcija se poziva za b i a % b, isto kao kod običnog algoritma.
4. Računanje koeficijenata: x i y dobijaju se iz rezultata rekurzivnog poziva.
5. Tuple: std::tuple omogućava da funkcija vrati tri vrednosti (NZD, x, y).

Za ulazne vrednosti a = 48 i b = 18 program ispisuje:

NZD: 6, x: -1, y: 3

Provera: 48 · (−1) + 18 · 3 = −48 + 54 = 6.

---

Vremenska složenost

• Euklidov algoritam (iterativni i rekurzivni): O(log min(a, b))
• NZS: isto kao NZD, uz jedno deljenje i jedno množenje
• Prošireni Euklidov algoritam: O(log min(a, b))

---

Veza sa drugim algoritmima

• Prosti brojevi i faktorizacija — NZD se može odrediti i iz prostih činilaca, ali je Euklidov algoritam mnogo brži
• Eratostenovo sito
• Osnovni matematički algoritmi

Regionalni centar za talente „Mihajlo Pupin”

Osnovna delatnost Regionalnog centra za talente jeste razvoj naučno-tehničkog i istraživačkog stvaralaštva mladih u oblasti prirodnih, tehničkih, društvenih i drugih nauka. Regionalni centar imao je cilj da formira opštinske jedinice za talente na teritoriji na kojoj deluje.

Posetite sajt Centra.

Korisni članci

• Sortiranje nizova
• Ugnježdene petlje u C/C++
• Nizovi u jeziku C/C++
• Funkcije u C/C++
• Pokazivači u C/C++
• Kreiranje Python web aplikacije
• ASP.NET Core web aplikacije
• Java predavanja
• Grafika u Javi