Euklido algoritmas

Euklido algoritmas pavaizduotas skaičiais 1599 ir 650

Euklido algoritmas – algoritmas surasti dviejų sveikųjų skaičių didžiausią bendrąjį daliklį (DBD), remiantis padalijimu iš liekanos. Algoritmas principas: pirmiausia didžiausias skaičius padalijamas su liekana iš mažiausio, o po to kiekviename tolesniame žingsnyje ankstesnės operacijos daliklis dalijamas iš gautos liekanos. Algoritmo rezultatas yra paskutinė gauta nenulinė liekana. Tai yra vienas iš seniausių žinomų algoritmų.

Istorija

Senovės graikų matematikas Euklidas, iš kurio vardo kilo šis algoritmas, iš pradžių suformulavo dviejų skaičių didžiausio bendrojo daliklio radimą geometriškai – kaip didžiausią bendrą dviejų atkarpų matą. Tokiu atveju iš ilgesnės atkarpos buvo atimama trumpiausia dalis, tada iš trumpesnės atkarpos atimama likusioji dalis ir taip toliau.

Tokia forma algoritmas pasirodė Euklido „Pradmenyse“ apie 300 pr. m. e. Nors taip pat buvo žinomas net 200 metų anksčiau. Pavyzdžiui, Aristotelis užsiminė apie šį algoritmą savo knygoje „Temos“ (gr. Τοπικων, Topikon) apie 330 pr. m. e.

Apibrėžimas

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