Евклидийн алгоритм

Евклидийн алгоритм гэдэг нь 2 натурал тооны хамгийн их ерөнхий хуваагчийг олох аргуудын нэг юм.

2 бодит тоо a, b (ab)-гийн хувьд ab-д хуваахад гарах үлдэгдлийг r гэвэл a ба b-гийн хамгийн их ерөнхий хуваагч нь b ба r-ийн хамгийн их ерөнхий хуваагчтай тэнцүү байдаг. Энэхүү шинж чанарыг ашиглан цааш br-д хуваахад гарах үлдэгдлийг олох гэх мэтээр явсаар үлдэгдэл нь 0 болох хүртэл үргэлжлүүлэн a ба b-гийн хамгийн их ерөнхий хуваагчийг олдог.

Энэ нь МЭӨ 300 оны орчимд бичигдсэн, Евклидийн "Эхлэл" зохиолын 7-р бүлгийн 1-3-т бичигдсэн байдаг.

Программ ашиглаж математикийн бодлого бодох үед ихэвчлэн ашиглагдана. Хамгийн түгээмэл алгоритмын нэг бөгөөд (a) дээд, (b) доод хязгаараас дөхөлт хийдэг онцлогтой.

Жишээ[засварлах | кодоор засварлах]

(Бодлого) 1071 ба 1029-ийн хамгийн их ерөнхий хуваагчийг ол.

  • 1071-ээс 1029-г хасахад гарах үлдэгдэл 42
  • 1029-г 42-т хуваахад гарах үлдэгдэл 21
  • 42-г 21-т хуваахад гарах үлдэгдэл 0

Иймд 1071 ба 1029-ийн хамгийн их ерөнхий хуваагч нь 21 болно.