Что за алгоритм "решето Эратосфена" и на чём он основан

Answer 1

Очень просто: Берешь все натуральные числа от 2 до некоторого N
Затем удаляешь из набора все, которые делятся на первое число - т. е. 2
Затем - на второе (это число 3)
Затем - на третье (а вот это уже будет 5, потому что 4 мы удалили на первом шаге) .
И струячишь дальше, до корня из N.
Таким образом у тебя остаются только простые числа в диапазоне 2-N.
Основан он на последовательном удалении чисел, заведомо не являющихся простыми, из набора, и на теореме о том, что любое непростое число может быть выражено как произведение некоторых простых.