[Paul Kellerman]

Листал намедни кое-что по теории чисел и возник вопрос...

Есть известный алгоритм "решето Эратосфена" для отсеивания
всех простых чисел в заданном ряду натуральных чисел 1...N

Кратко напомню суть:

Пусть задан ряд натуральных чисел: 1,2,3,4,...,N

Сначала сразу вычеркиваем 1 - оно не считается простым.
Далее, вычеркиваем все числа кратные 2, кроме самой 2.
Далее, вычеркиваем все числа кратные 3, кроме самой 3.
Далее, вычеркиваем все числа кратные 4, кроме самой 4
Далее, вычеркиваем все числа кратные 5, кроме самой 5
И так далее...

На примере ряда 1...25:

1) *2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 ,21,22,23,24,25

2) *2,3,5,7,9,11,13,15,17,19,21,23,25

3) *2,3,5,7,11,13,17,19,23,25

4) *2,3,5,7,11,13,17,19,23,25

5) *2,3,5,7,11,13,17,19,23

уже на 5-й итерации остались одни простые числа...

Также мы видим что 4-я итерация была впустую, числа кратные 4-м
были вычеркнуты ранее, когда вычеркивались числа кратные 2. Оно
и понятно, само число 4 составное и оно кратно 2. Но здесь ничего
не поделаешь, чтобы знать, какие номера итераций пропускать, при-
дется проверять на простоту сами номера - а это долго и сложно.

Интересен другой вопрос: до каких пор заниматься вычеркиванием?
Первое что приходит в голову: ну, крутить алгоритм для всех номеров
итераций начиная с 2 до N - это типа гарантированно обеспечит вы-
черкивание всех составных чисел.

На самом же деле - необязательно крутить алгоритм от 2 до N.
Необходимо и достаточно, прокрутить алгоритм от 2 до K - где
К - целая часть от N^0.5 (корень квадратный из N), чтобы в ряду
из N натуральных чисел остались только простые. Это проверено
и работает гарантированно для любого N. Но буду признателен
если кто-нибудь кинет ссылку на математическое доказательство
этого утверждения. Наверняка, это давно заметили и доказали.