Эратосфены тор нь анхны тоонуудыг олох хамгийн эртний бөгөөд хамгийн үр ашигтай алгоритмуудын нэг юм. Энэхүү алгоритмыг эртний Грекийн математикч Эратосфен хоёр мянга гаруй жилийн өмнө зохиосон бөгөөд өнөө үед компьютерын шинжлэх ухаан болон математикт өргөн ашиглагддаг юм. Энгийн ойлгомжтой хэдий ч би лав энэ алгоритмыг хамгийн гайхамшигтай нь гэж хэлнэ. Тодорхой хязгаар хүртэлх бүх анхны тоог хурдан олоход энэ алгоритм маш тохиромжтой байдаг билээ.
Анхны тоо гэдэг нь 1 болон өөрөөрөө л хуваагддаг, 1-ээс их эерэг бүхэл тоог хэлнэ. Жишээлбэл 2, 3, 5, 7 зэрэг нь анхны тоонууд юм. Анхны тоо эсэхийг шалгах хамгийн энгийн арга бол тухайн тоог жижиг тоонууд дээр хувааж үзэх явдал байдаг. Гэвч энэ арга нь тоо ихсэх тусам удаан ажилладаг сул талтай. Иймээс илүү хурдан бөгөөд оновчтой алгоритм хэрэгтэй болдог.
Эратосфены тор алгоритм нь анхны биш тоонуудыг дараалан “шигшиж” хасах зарчмаар ажилладаг. Эхлээд бүх тоог анхны гэж үзнэ. Дараа нь 2-оос эхлэн түүний бүх үржвэрүүдийг анхны биш гэж тэмдэглэнэ. Үүний дараа дараагийн тэмдэглэгдээгүй тоо болох 3 дээр мөн адил үйлдлийг хийдэг. Энэ үйл явц нь тухайн хязгаарын квадрат язгуур хүртэл үргэлжилнэ. Эцэст нь тэмдэглэгдээгүй үлдсэн тоонууд нь анхны тоонууд болдог. Энэхүү алгоритм нь ойролцоогоор O(n log log n) хугацааны нийлмэлтэй ажилладаг тул маш хурдан алгоритмд тооцогддог.
Өнөө үед Эратосфены шигшүүрийг программчлалын олимпиад, криптограф болон математик судалгаанд өргөн ашиглаж байна. Ялангуяа олон анхны тоог богино хугацаанд олох шаардлагатай бодлогуудад маш үр дүнтэй байдаг. Мөн энэхүү алгоритм нь энгийн санааг хэрхэн оновчтой аргаар хэрэгжүүлж болохыг харуулдгаараа суралцагчдад ихээхэн ач холбогдолтой. Хэдэн мянган жилийн өмнө зохиогдсон ч өнөөг хүртэл практикт хэрэглэгдсээр байгаа нь энэ алгоритмын үнэ цэнийг илтгэнэ.
