Euklidov algoritam za određivanje NZD

Ponekad je korisno odrediti NZD dva prirodna broja. Postupak koji je pokazan u osnovnoj školi je ispravan ali nedovoljno brz ako je reč o jako velikim brojevima.

Postupak koji se pripisuje Euklidu (4 v.pn.e.) zasniva se na činjenici da ako je a>b važi
NZD(a,b) = NZD(b,a mod b), gde je a mod b ostatak pri celobrojnom deljenju a sa b. Postupak se završava kada je b=0 i rešenje je broj a.

Ilustracija: NZD(1240, 860) = NZD(860, 380) = NZD(380, 100) = NZD(100, 80) = NZD(80, 20) = NZD(20, 0) = 20

PROGRAM u C-u:

#include <stdio.h>

int main()
{
    int a,b;
    scanf("%d %d", &a, &b);
    if(a<b)
    {
        int x=a;
        a=b;
        b=x;
    }
    while(b)
    {
        int ostatak = a%b;
        a = b;
        b = ostatak;
    }
    printf("%d",a);
    return 0;
}

Pošto je neke operacije jednostavnije opisati u C++ evo rešenja i u tom jeziku:

#include <iostream>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    if(a>b)
    {
        int x=a;
        a=b;
        b=x;
    }
    while(b)
    {
        int ostatak = a%b;
        a = b;
        b = ostatak;
    }
    cout << a;
    return 0;

}

Napomenimo da se NZS može računati na osnovu svojstva da je proizvod NZD i NZS za dva broja isti kao i proizvod tih brojeva.

Ilustracija: NZD(6,8) x NZS(6,8) = 2 x 24 = 48 = 6 x 8