Простые числа. Решето Эратосфена

Предположим, что нам требуется найти все простые числа, лежащие на отрезке натурального ряда от 1 до некоторого числа N, например от 1 до 100. Способ исключения из этого промежутка всех составных чисел был известен еще греческому математику Эратосфену (276- 194гг. до н. э.) и носит название решето Эратосфена:

• Выписать все натуральные числа от 2 до N.
• Вычеркнуть 2 и далее каждое второе число, затем вычеркнуть 3 и каждое третье число.
• Продолжать этот процесс, пока возможно, выбирая всякий раз первое оставшееся не вычеркнутым число, следующее за тем, кратные которому были вычеркнуты последними.
• Числа, которые остались не вычеркнутыми, составляют множество всех простых чисел на отрезке от 1 до N.
  Для N=100 имеем следующую таблицу: