Euklido algoritmas

Šiam straipsniui ar jo daliai trūksta išnašų į šaltinius (pažymėtas nuo 2020 m. lapkričio). Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

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

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

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

• $A$ ← $B$
• $B$ ← $A$ dalybos iš $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