Вопрос по теории чисел

[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. Но буду признателен
если кто-нибудь кинет ссылку на математическое доказательство
этого утверждения. Наверняка, это давно заметили и доказали.

[vega]

Это действительно заметили давно.
В четвертом номере журнала "Квант" за 1987 год Г.А.Гальперин упоминает о том, что первым математиком, указавшим на данный факт, был Фибоначчи. Упоминается это свойство практически во всех учебниках по теории чисел (например, Виноградов И.М. Основы теории чисел. - М.:Наука, 1972), но в большинстве случаев считается очевидным, а потому особенно и не доказывается...
Ничего не мешает провести доказательство самому, оно действительно несложное.
Примерно так:
1) Если N=a*b, то меньшее из двух чисел a, b - не больше [N^(1/2)]
Действительно, если a>[N^(1/2)] и b>a>[N^(1/2)], то a*b>N.
Итак, min(a;b)<=[N^(1/2)]
2) Если a (меньшее из двух чисел) делит N (т.е. N=a*b для некоторого b),
то, очевидно, b делит N, т.е. делимость на b (большее из двух чисел)
проверять не нужно.

[Paul Kellerman]

vega

Заметили давно то, что для проверки числа на простоту,
достаточно проверить его делимость нацело на числа от
2 до [N^0.5]. А в решете Эратосфена я что-то не заметил
никаких подобных проверок на простоту, в нем идея другая
- вычеркивание чисел по определенному алгоритму, вопрос
в том до каких пор этот алгоритм продолжать. Проверять на
простоту число N и выделять среди ряда N чисел все простые
с помощью решета Эратосфена - далеко не одно и то же.

[deyatinor]

http://alglib.sources.ru/numbers/erat.php http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80% D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0 Не знаю, поможет ли.
Примечание от себя: если реализовывать ряд при помощи битовых полей, то там сразу видно, какие итерации пропускать. Правда, к математическому доказательству это не имеет никакого отношения:(

[Paul Kellerman]

deyatinor

Спасибо. Я как-то сразу не подумал, делал строго так, как в книге был
описан алгоритм. А на самом деле, если мы допустим используем массив
A(i), i = 1...N, и на каждой итерации в качестве вычеркивания исполь-
зуем просто занесение нуля на место составного числа, то потом при
переходе к следующей итерации можно просто проверить соответ-
ствующую ячейку A(k), где k - номер новой итерации, если ячейка = 0,
то значит итерацию смело пропускаем и переходим к следующей.

[vega]

Хм... Возможно, я не вполне понял вопрос...
Решето Эратосфена вполне можно использовать для
проверки N на простоту (другое дело, что есть алгоритмы и получше).
Если N простое, то для того чтобы это выявить, алгоритм придется
выполнять полностью - до [N^(1/2)]. Если же N - составное, то,
конечно же, оно будет вычеркнуто раньше, чем доберемся
до этой границы.
Если вопрос был в том, насколько раньше это произойдет при составном N,
то от моего ответа пользы не так много...

[Paul Kellerman]

vega

Я говорил только о выделении простых чисел в заданном ряде
натуральных чисел от 1 до N, путем вычеркивания составных,
с помощью решета Эратосфена - наиболее простого метода.

Вопрос проверки на простоту не ставился. Вопрос касается
только именно решета Эратосфена: до каких пор заниматься
отсеиванием. Причем сам ряд натуральных чисел от 1 до N
может быть задан для произвольного N, вовсе необязательно
только простого. N - может быть любым натуральным числом.

Не спешите так аппелировать к кажущимся очевидностям.
Нужно строгое доказательство следующего утверждения:

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

[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. Дорогие девочки, девушки и дамы! Поздравляю вас с наступающим
праздником. От всей души желаю вам счастья, удачи, любви и тепла.

[VesterBro]

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