Эвклид бол эртний Грекийн алдартай математикчдын нэг бөгөөд геометрийн шинжлэх ухааны үндсийг бичсэн хүн юм. Түүний бичсэн "Elements" бүтээл нь олон зууны турш математикийн суурь сурах бичиг болон ашиглагдсан билээ. Эвклид зөвхөн геометрийн салбарт төдийгүй тооны онолд чухал хувь нэмэр оруулсан. Түүний нэрээр нэрлэгдсэн Эвклидийн алгоритм нь өнөөдөр ч програмчлал, алгоритмын бодлогод өргөн хэрэглэдэг энгийн хэрнээ хүчтэй арга юм.
ХИЕХ буюу хоёр тооны хамгийн их ерөнхий хуваагч гэдэг нь тухайн хоёр тоог хоёуланг нь хувааж чаддаг хамгийн том бүхэл тоог хэлнэ. Жишээлбэл, 18 ба 24-ийн ерөнхий хуваагчид 1, 2, 3, 6 байдаг бөгөөд хамгийн том нь 6 тул ХИЕХ нь 6 байна. Үүнийг олох хамгийн энгийн арга бол 1-ээс эхлээд хоёр тооны бага хүртэл бүх тоог шалгах явдал юм. Хэрэв тухайн тоо хоёуланг нь хувааж байвал хариунд хадгална. Гэхдээ энэ арга нь том тоон дээр удаан ажиллана. Үүнийг Эвклид манай эрний өмнөх 200 онд шийдсэн байна.
Эвклидийн алгоритм нь хиех-ийг илүү хурдан олох ухаалаг арга юм. Үндсэн санаа нь: хоёр тооны хамгийн их ерөнхий хуваагч нь том тоо болон том тоог жижиг тоонд хуваасан үлдэгдэл гэсэн 2 тооны ХИЕХ-тэй тэнцүү байна. Өөрөөр хэлбэл, gcd(a, b) = gcd(b, a % b) гэсэн үг. Энэ үйлдлийг үлдэгдэл 0 болох хүртэл давтана. Үлдэгдэл 0 болсон үед үлдсэн тоо нь хоёр тооны GCD болно. Ийм учраас олон удаа бүх хуваагчийг шалгах шаардлагагүй болж, алгоритм маш хурдан ажилладаг.
Програмчлалд математик ийм байдлаар маш хүчтэй хэрэгсэл болдог. Зарим бодлогыг шууд хүчээр шалгавал удаан ажиллах боловч математик шинж чанарыг нь ойлговол хэдхэн мөр кодоор хурдан шийдэж болно. Эвклидийн алгоритм нь үүний тод жишээ юм. Энэ алгоритмыг бутархай хураах, LCM олох, тооны онолын бодлого бодох, модуль арифметик ашиглах зэрэг олон нөхцөлд хэрэглэж болно. Тиймээс жижиг алгоритм мэт харагдавч, цаанаа маш гүн математик санаа агуулсан байдаг.
