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

Доброго времени суток, товарищи! Сегодня я продолжу речь про простые числа, а именно, расскажу про Решето Эратосфена. Когда-то давным-давно древнегреческому математику Эратосфену Киренскому пришла в голову одна замечательная идея, который мы пользуемся и по сей день. Суть состоит в том, чтобы находить все простые числа до какого-то заданного n, вычеркиванием составных чисел. *составное число - число, которое можно представить в виде с = a*b, где ни a ни b не являются 1* Представим, что мы уже знаем, что 2 (первое простое число) - простое число...