Euklido algoritmas
![]() |
Šiam straipsniui ar jo daliai trūksta išnašų į šaltinius. 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ų ir DBD rasti užrašomas taip:
- Jeigu yra nulis, tuomet DBD yra
- Kitaip,
- ←
- ← dalybos iš 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;