Euklido algoritmas

Euklido algoritmas – algoritmas, kurio autorystė prisikiriama Euklidui, skirtas surasti dviejų skaičių didžiausią bendrą daliklį (DBD).

Algoritmas dviejų skaičių $A$$A$ ir $B$$B$ DBD rasti užrašomas taip:

• Jeigu $B$$B$ yra nulis, tuomet DBD yra $A$$A$
• Kitaip,

• $A$$A$ ← $B$$B$
• $B$$B$ ← $A$$A$ dalybos iš $B$$B$ liekana

• Kartojame nuo pirmo žingsnio

Šio algoritmo realizavimas Pascal programavimo kalba:

 while (a > 0) and (b > 0) do
   if a > b then a := a mod b
            else b := b mod a;
 dbd := a + b;

C/C++ kalba:

 while (abs(a) && abs(b))
   if (abs(a) > abs(b)) a %= b; 
         else b %= a;
 dbd = a + b;

Taip pat skaitykite

• Išplėstinis Euklido algoritmas