Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Что такое решето Эратосфена, знает сегодня, пожалуй, любой школьник, интересующийся математикой. Но не всякий знает, какова алгоритмическая сложность этого «просеивателя». Напомним условие задачи Необходимо найти все простые числа, меньшие или равные заданному числу N. Запишем в ряд все числа от 1 до N и будем вычёркивать оттуда все числа, кратные двойке, но больше двойки, затем, все числа, кратные тройке, но больше тройки и т...

(На "Хабре" этот же мой материал) Об античном ученом Эратосфене Киренском, которому приписывают наш метод, википедия говорит следующее [1]: «Эратосфен Киренский (др.-греч. ἘρατοσθένηςὁΚυρηναῖος; 276 годдон. э.—194 годдон. э.) —греческий математик, астроном, географ, филолог и поэт. Ученик Каллимаха, с 235 г. дон. э. —глава Александрийской библиотеки. Первый известный учёный, вычисливший размеры Земли.» Обычно метод Эратосфена описывают при помощи картинки, где изображено некоторое количество первых...