Eiklīda algoritms

Eiklīda algoritms skaitļu teorijā ir efektīvs algoritms divu veselu skaitļu lielākā kopīgā dalītāja (LKD) atrašanai, kas balstīts uz dalīšanu ar atlikumu. Algoritms ir šāds: vispirms nepilni izdala lielāko skaitli ar mazāko un tad katrā nākamajā solī iepriekšējās darbības dalītāju dala ar iegūto atlikumu. LKD ir pēdējais iegūtais nenulles atlikums.

Eiklīda algoritms attēlots ar skaiļiem 1599 un 650

Ievērojami ir tas, ka algoritmam nav nepieciešams sadalīt skaitļus pirmreizinātājos, kā arī tas, ka šis ir viens no vecākajiem zināmajiem algoritmiem.

Piemērs

Jāatrod lielākais kopīgais dalītājs. $LKD(336,287)=?\$

• $336:{\color {Magenta}287}=1,atl.\color {red}49$
• ${\color {Magenta}287}:{\color {red}49}=5,atl.\color {blue}42$
• ${\color {red}49}:{\color {blue}42}=1,atl.\color {Magenta}\mathbf {7}$
• ${\color {blue}42}:{\color {Magenta}7}=6,atl.\mathbf {0}$

Tā kā pēdējais skaitlis, ar kuru dalīja un nebija atlikums, ir 7, tad $LKD(336,287)=7$.

Vēsture

Sengrieķu matemātiķis Eiklīds, no kura vārda cēlies šī algoritma nosaukums, divu skaitļu LKD atrašanu sākotnēji formulēja ģeometriski — kā divu nogriežņu lielākā kopīgā mēra atrašanu. Tādā gadījumā no garākā nogriežņa tika atņemts īsākais, tad atlikums tika atņemts no īsākā nogriežņa un tā tālāk.

Šādā formā algoritms parādījās Eiklīda "Elementos" apmēram 300. gadā p.m.ē. Tomēr, iespējams, ka tas jau bija zināms pat 200 gadus agrāk. Piemēram, Aristotelis devis mājienu par šo algoritmu savā grāmatā "Tēmas" (Τοπικων, Topikon) apmēram 330. gadā p.m.ē.