Sieve of Eratosthenes тухай. N тоог анхны тоо эсэхийг sqrt(N) үйлдлээр шалгаж болно. Тэгвэл 1-с N хүртэлх бүх анхны тоог ол гэсэн бол үүнийг ашиглавал ойролцоогоор N*sqrt(N) үйлдлээр хийх юм. Одоо бичих алгоритм нь илүү хурдан юм. Анхны тоо гэдэг нь зөвхөн 2 ширхэг натурал тоон хуваагчтай тоо ба өөрөөр хэлбэр анхны тоо нь өмнөх ямар ч анхны тоондоо хуваагддаггүй гэсэн үг. 2-г хамгийн эхний анхны тоо гэдгийг мэднэ. Тэгвэл 2-д хуваагддаг дараагийн бүх тоонууд анхны тоо болж чадахгүй. Тэгвэл энэхүү тоонуудыг анхны тоо биш гэж тэмдэглэе. Дараагийн тоо нь 3 ба энэ нь өмнөх бүх анхны тоондоо хуваагдаагүй тул энэ тоо нь анхны тоо. Тэгвэл 3-д хуваагддаг дараагийн бүх тоонууд анхны тоо биш. Дараагийн тоо нь 4 ба энэ нь 2-д хуваагддаг тул анхны тоо биш гэж тэмдэглэгдсэн. Дараагийн тоо нь 5 ба энэ нь анхы тоо биш гэж тэмдэглэгдээгүй ба өмнөх бүх анхны тоондоо хуваагдаагүй тул анхны тоо. Тэгвэл 5-д хуваагддаг дараачийн тоонууд нь анхны тоо биш болох юм. Энэ мэтчилэн бодвол хугацааны үнэлг
Алгоритмын хичээл