[Paul Kellerman]

На выходных навеяло...
Проект доказательства.

Применим метод математической индукции.

1) Для N = 1, 2 и 3 проверять толку мало, так при этом
[N^0.5] = 1, а мы начинаем отсев с чисел кратных 2.

Так что начнем индукцию не с N = 1, а с N = 4 (тем более,
математики знают, что обобщенный метод матиндукции
начинает проверку общей формулы для произвольного
стартового N = s, далее сделав допущение что формула
верна для N = r, причем r > s, проверяет при N = r + 1.

При N = 4, [N^0.5] = 2. Соответственно, алгоритм сработает
только один раз - итерация отсева чисел кратных 2. На этой
итерации будет отсеяно единственное составное число 4, так
что при N = 4 - алгоритм работает правильно.

2) Теперь допустим, что при N = K алгоритм тоже работает верно -
отсев чисел кратных 2,3,...,[K^0.5] обеспечивает удаление всех
составных чисел из множества натуральных чисел 1...K. Теперь,
исходя из этого попробуем доказать, что при N = K + 1 алгоритм
тоже обеспечит удаление всех составных.

Проще говоря, мы имели исходное множество натуральных чисел
1...K, а теперь добавили в конец еще одно (K + 1)-ое число. При
этом отсев теперь ведется по числам кратных 2,3,...,[(K+1)^0.5].
Очевидно, что множество 2,3,...,[(K+1)^0.5], по крайней мере, не
меньше чем множество 2,3,...,[K^0.5], т.к. [K^0.5] <= [(K+1)^0.5],
Тогда, исходя из нашего вышеприведенного допущения следует,
что в подмножестве 1...K множества 1...K+1 все составные числа
будут удалены. Остается исследовать только самое число (K + 1).

Здесь возможны только четыре ситуации, требующие рассмотрения:

a) (K + 1) - простое, причем [(K+1)^0.5] = [K^0.5] + 1
б) (K + 1) - простое, причем [(K+1)^0.5] = [K^0.5]
в) (K + 1) - составное, причем [(K+1)^0.5] = [K^0.5] + 1
г) (K + 1) - составное, причем [(K+1)^0.5] = [K^0.5]

Итак, ситуации а) и б) не представляют особой сложности, поскольку
если число (K + 1) - простое, то оно по определению не будет кратно
ни одному из чисел 2,3,...,[(K+1)^0.5] и, соответственно, оно не будет
удалено при проведении итераций отсева - так и должно быть.

В ситуации в) число (К + 1) составное и оно обязательно подлежит
удалению. При этом мы имеем условие [(K + 1)^0.5] = [K^0.5] + 1.
Однако, нетрудно заметить, что такое условие возможно, только
если (K+1)^0.5 - целое число (корень дает целое число), K^0.5 -
нецелое число, меньшее (K+1)^0.5 (которое целое!), в этой ситу-
ации целая часть от K^0.5 будет ровно на 1 меньше (K+1)^0.5.
Но тогда, раз (K+1)^0.5 - целое, то [(K + 1)^0.5] = (K + 1)^0.5, а
[(K + 1)^0.5]^2 = ((K + 1)^0.5)^2 = K + 1. Поскольку же алгоритм
работает при 2,3,...,[(K + 1)^0.5], а [(K + 1)^0.5] = (K + 1)^0.5, и
это целый корень квадратный из числа (K + 1), то очевидно оно
является целым сомножителем числа (K + 1), и тогда число (K + 1)
будет удалено - так и должно быть.

В ситуации г) число (К + 1) составное и оно обязательно подлежит
удалению. При этом мы имеем условие [(K + 1)^0.5] = [K^0.5]. Это
условие возможно только если (K + 1)^0.5 - нецелое (корень дает
нецелое число), при этом K^0.5 - может быть целым или нецелым,
это не имеет значения. В противном случае если (K + 1)^0.5 целое
то [(K + 1)^0.5] = [K^0.5] + 1. Но если (K + 1)^0.5 - нецелое, тогда
составное число (K + 1) при разложении на два целых сомножителя
будет иметь один из сомножителей меньший, чем (K + 1)^0.5. Более
того, меньший сомножитель - число целое и значит <= [(K + 1)^0.5].
Поскольку алгоритм ведет отсев для чисел кратных 2,3...[(K + 1)^0.5]
то алгоритм обязательно на одной из итераций попадет на число,
являющееся меньшим сомножителем числа (K + 1), и число (K + 1)
будет отсеяно - так и должно быть.

Таким образом, мы рассмотрели все четыре случая и убедились, что
если число K + 1 простое, то оно сохраняется, а если составное, то
оно удаляется. Удаление всех составных чисел среди подмножества
1...K обеспечивается допущением индукции. Таким образом, сделав
допущение что алгоритм работает верно при N = K, мы увидели что
он также работает и при N = K + 1.

Утверждение доказано. PavelAR (c), 2006.

P.S. Дорогие девочки, девушки и дамы! Поздравляю вас с наступающим
праздником. От всей души желаю вам счастья, удачи, любви и тепла.