Решето Эратосфена

Грек Эратосфен ещё до нашей эры придумал алгоритм поиска простых чисел до заданного предела: пишешь все числа от 2 до N и потом "просеиваешь" остальные.

Механика простая: берёшь 2, вычёркиваешь все его кратные (буквально считая раз, два (чик), раз, два (чик), раз, два (чик)). Потом берёшь 3, вычёркиваешь все его кратные (тоже: раз, два, три (чик), раз, два, три (чик)). И так далее до корня из N (потому что всё что больше корня из N считать бесполезно).

Обычно это первый алгоритм который дают закодить на каких-нибудь околоматематических курсах программирования, и хотя это не самый оптимальный алгоритм, он очень простой и живёт с нами до сих пор как некоторый способ замерить быстроту компьютера — в конце концов, они для перебирания чисел и придумывались, верно? Верно?

Любопытно, что "простые" числа несмотря на их простоту будоражат умы — есть, ещё пара решетов более современных решето Притчарда (1979), Сундарама (1934), Аткина (2003). Я долго не понимал почему, собственно, пока не буквально приоткрыл книжку по теории чисел и не почитал там про модульную арифметику. Не сказать что я стал лучше понимать что-то, но прикольно что такая математика до сих пор с нами и вокруг нас, конечно.

А Эратосфен вроде как ещё и один из первых измерил окружность Земли просто наблюдая за тенью в колодце, но этим он никому не запомнился, сито поприкольнее как-то. Пожалуй, можно сказать что это хорошая история про важность реквизита.