Euklido algoritmas

Suskaičiuoja dviejų skaičių didžiausią bendrąjį daliklį.

x ir y DBD apskaičiuojamas taip:

1. jeigu x = 0, tai DBD yra y
2. jei ne, tai:
   1. jeigu x > y:
      1. x priskiriame y reikšmę
      2. y priskiriame ankstesnę x reikšmę (sukeičiame x ir y vietomis)
   2. atėmę y iš x gauname naująją x reikšmę (visada atimame mažesnį iš didesnio, todėl juos ir reikia prieš tai sukeisti)
   3. kartojame pirmąjį žingsnį (1.)

x = 160, y = 75, koks DBD?

1. x > y, x = 160 - 75 = 85, y = 75
2. x > y, x = 85 - 75 = 10, y = 75
3. x < y, x = 10, y = 75 - 10 = 65
4. x < y, x = 10, y = 65 - 10 = 55
5. x < y, x = 10, y = 55 - 10 = 45
6. x < y, x = 10, y = 45 - 10 = 35
7. x < y, x = 10, y = 35 - 10 = 25
8. x < y, x = 10, y = 25 - 10 = 15
9. x < y, x = 10, y = 15 - 10 = 5
10. x > y, x = 10 - 5 = 5, y = 5
11. x = y, t.y. x nėra mažesnis už y, x = 5 - 5 = 0, y = 5
12. x = 0

Ats.: 5

program Euklidas;
 
    var x, y : integer;
 
function gcd (u, v : integer) : integer;
        var t : integer;
 
    begin
        repeat
            if (u < v) then begin
                t := u;
                u := v;
                v := t;
            end;
            u := u - v;
        until u = 0;
        gcd := v;
    end;
 
 
begin
 
while not eof do begin
    readln (x, y);
    if ((x > 0) and (y > 0)) then
        writeln (x, ' ', y, ' ', gcd (x, y));
end;
 
end.

• Euklido algoritmas
• Išplėstinis Euklido algoritmas