Простые числа - часть 2

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