Трухин С.Л.

АЛГОРИТМ

ОПРЕДЕЛЕНИЯ ПОРЯДКОВОГО НОМЕРА ПРОСТОГО ЧИСЛА

ПО ЗНАЧЕНИЮ ЭТОГО ПРОСТОГО ЧИСЛА

И

ПОИСК ПРОСТОГО ЧИСЛА ПО ЕГО НОМЕРУ

Вступление.
Предлагаемый алгоритм очень прост, он прост по своей структуре и основан на простой идее. Для его доказательства используется элементарный математический аппарат и для освоения и практического использования алгоритма не требуется каких-либо специальных математических знаний, выходящих за рамки обычного школьного курса. Задачи, которые, так или иначе, затрагиваются алгоритмом, учитывая историю математики, нельзя отнести к разряду простых. И, тем не менее, оказывается, можно получить очень интересные результаты в этом направлении весьма простым способом. Кстати, алгоритм может добавить хлопот соревнующимся в поиске самых больших значений простых чисел, потому, что отныне организаторы подобных соревнований могут добавить требование указывать порядковые номера найденных простых чисел.

Предупреждая дискомфортные ощущения, которые могут возникнуть у продвинутых в математическом плане читателей, спешу сообщить, что я – не научный сотрудник, не математик и даже не отношу себя к любителям математики (поэтому некоторые из моих высказываний могут быть легкомысленными и ими можно пренебречь). Но так случилось, что на протяжении ряда лет любителем одной единственной математической головоломки я, все же, был. И в эту проблему, пленником которой я стал, превратился, со временем, алгоритм собственного изобретения. Впрочем, к нему я периодически охладевал, затем вновь возвращался, и, таким образом, у меня всегда в запасе было, в дополнение к другим моим увлечениям и развлечениям, еще одно очень интересное занятие. А началось все так – однажды у меня появилась одна очень интересная идея (не связанная с простыми числами). Но, поскольку, просчитать ее теоретически я не мог, а построение экспериментальной модели требовало существенных материальных затрат, у меня возникли сомнения – а стоит ли мне вообще, в принципе, заниматься подобными вещами, способен ли я решить какую-либо неординарную задачу? И я решил протестировать самого себя на предмет сообразительности, а тестом избрал формулу простого числа (всего лишь!). Отрицательный результат позволил бы мне расценивать в будущем любые свои необычные идеи, как бесплодные мечтания. Для решения задачи пришлось использовать в качестве инструмента то, чем располагал – еще сохранившиеся некоторые сведения из элементарной математики и начал матанализа. Причем, чтобы не зацикливаться на чужих идеях, а также случайно не впасть в плагиат, я решил решать задачу абсолютно самостоятельно, не заглядывая предварительно ни в какие источники информации о простых числах, кроме таблицы простых чисел. Все, что мне было известно о простых числах до этого, было озвучено когда-то давно, еще в школьные годы, преподавателем нашего местного пединститута на факультативной лекции о простых числах. По-видимому, лекция была очень хорошей и оставила на всю жизнь неизгладимое впечатление. Помнится, очень обидно было, что Ферма постигла неудача, и что до конца жизни ему так и не удалось добиться желаемого результата …

Гораздо позже, когда в общих чертах результат изысканий обозначился в виде алгоритма, однажды, скользя по Интернету, я вроде бы наткнулся на информацию (что-то вроде теоремы) о невозможности существования формулы простого числа – точно не берусь утверждать, действительно ли существует такая теорема и доказана ли она. Может быть, речь шла о непрерывности функции зависимости значения числа от его номера. Увидел бы что-то подобное раньше – изучил бы вопрос детальнее и, пожалуй, не взялся бы изобретать «вечный двигатель». Но информация попалась на глаза несвоевременно, точнее, слишком поздно и оказалась просто неактуальной. Ну, а ранее, прежде чем сдаться, удовлетворившись алгоритмом вместо вожделенной формулы, пришлось достаточно долго поупражняться в решении различных головоломок (правильнее было бы сказать «потрудиться», а не «поупражняться», но словом «труд» часто обозначают рутинное и малоприятное занятие по принуждению, в данном же случае рутины было предостаточно, но рутины приятной и исключительно на добровольной основе). Когда алгоритм был сформирован в общих чертах, возник вопрос, а стоит ли вообще фиксировать результат – содержимое будущей статьи по своему характеру явно обещало быть похожим на решение задачи уровня школьной олимпиады. Несколько попыток, правда, не очень усердных, обнаружить в сети что-либо похожее не увенчались успехом. Но, зато оказалось, что многие фрагменты моего доморощенного алгоритма давным-давно придуманы другими людьми (впрочем, странно, если бы было не так). Не могу сказать, что эти новости меня обрадовали или слишком огорчили, но надо признать, легкий налет досады присутствовал. Как коротко прокомментировать мою реакцию? Пожалуй, уместна фраза (которая тоже не мной придумана): «Человеческая жадность безгранична». Утешало то обстоятельство, что, всё же, все эти фрагменты изыскивались разными людьми и в разные времена, а мне посчастливилось повторить их оптом. В первую очередь сказанное относится к «решету» Эратосфена. Мой алгоритм, по сути, отталкивается от этой идеи, можно сказать, основан на ней. Хотя подходы к открытию «решета» у Эратосфена и у меня, скорее всего, были разными. Я, например, натолкнулся на это «решето» «случайно», экспериментируя, однажды, с формулами бегущей волны вдоль числовой оси. С бегущими волнами так ничего и не получилось, но появились разноцветные синусоиды. Эратосфен же, возможно, о синусоидах еще и представления не имел. Далее, Эратосфен отбрасывал составные числа в результате просеивания, сосредотачивая внимание на простых числах, я же, наоборот, фактически исключил из рассмотрения простые числа, сосредоточившись на подсчете составных. Учитывая то, что идея «решета» Эратосфена оказалась единственной дельной идеей из огромного количества экспериментов, у меня даже появился соблазн предположить – а не является ли эта идея для простых чисел фундаментальной? Впрочем, данная гипотеза тоже относится к разряду легкомысленных, но если вдруг когда-нибудь она подтвердится, то, безусловно, ее можно будет назвать дальновидной. Кроме выше описанного грандиозного эпизода имели место и другие повторные «открытия». Например, интервал с его особенными свойствами, который для удобства изложения я назвал «опорным» (наверное, по аналогии с опорным трезвучием), равенство единице суммы знакопеременных биномиальных коэффициентов, способ формирования всех возможных сочетаний из определенного множества чисел (правда, о последнем не довелось встретить каких-либо упоминаний) и т.п. Догадки, возможно, вовсе и не выдающиеся, чтобы о них писать. Но хочу заметить, что в процессе продвижения к главной цели всегда встречаются маленькие открытия, а маленькие открытия восхищают не меньше, чем большие! От прагматично настроенных людей я несколько раз слышал вопрос, что мною движет, зачем я ищу формулу простого числа, и если я ее найду, то, что из этого? Мне думается, что каждым исследователем движет не только ожидание эффекта от будущего результата, скажем, какая-то практическая его ценность или значимость в плане теории. В большей степени увлекает сам процесс поиска чего-то нового и неисследованного. Похоже, так же, как и в музыке, людей пленяет всякая гармония, в том числе и гармония, несомненно, присутствующая в волшебной последовательности простых чисел. Гармонией пронизан весь мир, в котором мы живем. Но, пока не установлены закономерности, гармония неизъяснима, и это не дает покоя.

Повторюсь, не будучи математиком, я долго не мог заставить себя оформить свои соображения в виде статьи, предназначенной для публикации, считая, что несколько неприлично с моей стороны пытаться привлечь к полученным результатам внимание людей, знающих предмет. Но что же делать, если внимания людей, не знающих предмета, привлечь к подобным вещам вообще невозможно? И я решил, если и не заявлять о своем алгоритме публично, то, поначалу, хотя бы зафиксировать его на каком-нибудь носителе, на всякий случай. Потом, рассудив о том, что качество содержимого статьи не соответствует уровню научного журнала, я принял решение поместить статью на сайт в Интернете. Допускаю, что описываемый алгоритм давно известен, либо существуют более изящные решения этой задачи. Если, все же, статья представляет интерес, то хотелось бы надеяться на снисхождение со стороны специалистов к стилю изложения материала и, возможно, недостаточно строгим, с математической точки зрения, доказательствам. Это не сказывается на достоверности окончательных выводов и результатов, а доказательствам, в случае необходимости, я уверен, можно придать более строгую форму – мне просто не хватает квалификации и терпения.

Как я уже говорил, для прочтения статьи достаточно знаний элементарной алгебры, чуть-чуть комбинаторики и арифметики. Это обстоятельство позволило адресовать статью широкому кругу читателей, включая школьников, поэтому, многие фрагменты алгоритма и доказательств объясняются, возможно, излишне подробно.

В некоторых ранних версиях Windows и Microsoft Office, для правильного отображения формул, возможно, понадобится активировать Редактор формул. Для этого в Microsoft Word достаточно найти в меню «Добавить или удалить кнопки» значок редактора – и перетащить его на панель задач.

Завершая вступление, хотелось бы поддержать дилетантов-энтузиастов, подобных мне. Несомненно, прежде пытаться заниматься научными исследованиями, следует вооружиться хорошими теоретическими знаниями, стать специалистом. Но, «специалист» – тоже понятие относительное. Поэтому, иногда следует, преодолев застенчивость и робость, решиться сделать «запретный» шаг в неизвестное…

Описание алгоритма.
§1. Используемые термины и обозначения.
Считаем простыми числами все целые числа, принадлежащие последовательности натуральных чисел, которые делятся нацело, без дробного остатка, только на самих себя и на 1. Причем, число 1 не относим к простым числам. Числа, которые делятся без остатка не только на самих себя и 1, но и на некоторые другие числа из последовательности натуральных чисел, считаем составными.

Последовательность простых чисел будем обозначать P_i, где i=1,2,3,…, – порядковый номер простого числа.

Известное простое число, неизвестный порядковый номер n которого требуется найти, обозначим P_n, где n может принимать значения 1,2,3,…,. И в обратной задаче, так же будем обозначать неизвестное простое число P_n, искомое по заданному порядковому номеру n, где n=1,2,3,…,.

Под закрытым интервалом понимаем отрезок на числовой оси от числа a до числа b, включая сами числа a и b, и обозначаем [a;b].

Под полуоткрытым интервалом понимаем отрезок на числовой оси от числа a до числа b:

- включая число a и не включая числа b, обозначаем [a;b);

- не включая числа a и включая число b, обозначаем (a;b].

Под открытым интервалом понимаем отрезок на числовой оси от числа a до числа b, не включая сами числа a и b, и обозначаем (a;b).

Целую часть любого дробного положительного числа обозначим .

Остальные символы и обозначения, в основном, являются общепринятыми во многих математических справочных и учебных пособиях.

По мере изложения материала иногда появлялась необходимость введения небольшого количества новых специфичных терминов и обозначений, назначение которых трудно объяснить в лаконичной форме в начале статьи.

§2. Справочная таблица простых чисел.
Приведем таблицу первых ста простых чисел, взятую из справочника. Для удобства пользования ею в дальнейшем, укажем подстрочным индексом порядковый номер каждого простого числа в последовательности простых чисел.

2₁ 3₂ 5₃ 7₄

11₅ 13₆ 17₇ 19₈ 23₉ 29₁₀ 31₁₁

37₁₂ 41₁₃ 43₁₄ 47₁₅ 53₁₆ 59₁₇ 61₁₈

67₁₉ 71₂₀ 73₂₁ 79₂₂ 83₂₃ 89₂₄ 97₂₅

101₂₆ 103₂₇ 107₂₈ 109₂₉ 113₃₀ 127₃₁ 131₃₂

137₃₃ 139₃₄ 149₃₅ 151₃₆ 157₃₇ 163₃₈ 167₃₉

173₄₀ 179₄₁ 181₄₂ 191₄₃ 193₄₄ 197₄₅ 199₄₆

211₄₇ 223₄₈ 227₄₉ 229₅₀ 233₅₁ 239₅₂ 241₅₃

251₅₄ 257₅₅ 263₅₆ 269₅₇ 271₅₈ 277₅₉ 281₆₀

283₆₁ 293₆₂ 307₆₃ 311₆₄ 313₆₅ 317₆₆ 331₆₇

337₆₈ 347₆₉ 349₇₀ 353₇₁ 359₇₂ 367₇₃ 373₇₄

379₇₅ 383₇₆ 389₇₇ 397₇₈ 401₇₉ 409₈₀ 419₈₁

421₈₂ 431₈₃ 433₈₄ 439₈₅ 443₈₆ 449₈₇ 457₈₈

461₈₉ 463₉₀ 467₉₁ 479₉₂ 487₉₃ 491₉₄ 499₉₅

503₉₆ 509₉₇ 521₉₈ 523₉₉ 541₁₀₀
§3. Задачи, решаемые с помощью алгоритма.
Алгоритм позволяет:
1. Определить порядковый номер любого простого числа, если заранее известно или доказано, что число является таковым.

2. Исследовать любое, произвольно выбранное, натуральное число, на предмет его принадлежности к простым либо составным числам. Если же исследуемое число оказывается составным, то алгоритм указывает номер наибольшего по величине простого числа в интервале от 2 до исследуемого числа и, впоследствии, позволяет выделить это простое число.

3. С помощью обоснованного прогноза и методом последовательного приближения, алгоритм и следствия, вытекающие из него, позволяют найти число, принадлежащее последовательности простых чисел, с любым произвольно заданным порядковым номером.


§4. Введение, или сущность метода, на котором базируется алгоритм.
Целесообразно при описании алгоритма придерживаться порядка, обозначенного в предыдущем параграфе. Можно было бы выстроить статью в виде последовательности лемм и теорем, т.е. в виде формул, алгебраических выражений и соответствующих доказательств. Но выбор такой формы создал бы трудности, как для изложения материала, так и для его восприятия. Думаю, если начать с описания частного случая на числовых примерах, это облегчит знакомство с алгоритмом, по крайней мере, на начальном этапе. Кроме того, такая форма введения отразит тот истинный путь, продвижение по которому и позволило, в конечном итоге, сформулировать алгоритм. Настоящий параграф посвящен подробному описанию первой задачи, обозначенной в §3.

Итак, требуется определить порядковый номер произвольно выбранного простого числа. Для иллюстрации выберем в таблице простых чисел число 101 и определим его номер, руководствуясь определенными соображениями. Какова основная идея? Последовательность натуральных чисел от 1 до 101 состоит из некоторого количества простых и некоторого количества составных чисел, плюс число 1 (не будем приводить доказательство или ссылаться на доказательство этого утверждения, как не будем останавливаться на доказательствах многих, уже доказанных утверждений, ставших очевидными). Общее же количество всех простых и составных чисел на отрезке [1;101] равно 100 (ведь натуральное число 1 не относится ни к составным числам, ни к простым). Если удастся найти количество составных чисел в интервале [2;101] и вычесть это число из общего количества натуральных чисел на указанном интервале, т.е. из 100, то получим некое число, равное количеству простых чисел в указанном интервале. Вот это некое число как раз и совпадает с номером самого большого по величине простого числа, стоящего на последнем месте в последовательности простых чисел на промежутке от 2 до 101, т.е. с порядковым номером простого числа 101. Как выделить составные числа? Можно воспользоваться «решетом» Эратосфена.

В общих чертах метод Эратосфена выглядит следующим образом (в силу простоты принципа я не буду сопровождать изложение чертежами, это легко сделать самостоятельно). Изобразим числовую ось и уделим особое внимание первому простому числу 2. Пометим все числа, кратные двум, кроме самого числа 2 (можно зачеркнуть их, отметить маркером, «крестиками» и т.д.). Эту операцию очень удобно выполнить, например, с помощью циркуля или измерителя, предварительно раздвинув его ножки на ширину, равную длине отрезка от 0 до 2. После этого «просеивания» ближайшим к двойке «уцелевшим» числом оказывается второе по порядку простое число 3. Тем же способом отмечаем все числа на числовой оси, кратные трем, не трогая самого числа 3. После этой операции ближайшим к числу 3 не зачеркнутым оказывается третье простое число 5, после него 7 и т.д. Постепенно зачеркиваются все составные числа и остаются не зачеркнутыми простые, которые можно свести в таблицу и, пересчитав по порядку, присвоить порядковые номера. Можно также пересчитать количество «крестиков» на выбранном интервале и определить количество составных чисел. Просто и наглядно, и нет необходимости производить какие-либо вычисления. Единственный недостаток – нужен очень «длинный» чертеж, если, к примеру, захочется найти простое число с номером 1000000.

Воспользуемся «решетом», немного изменив способ маркировки составных чисел, пользуясь не измерителем, а «запуская» в качестве маркера вдоль оси от нуля синусоиды (разноцветные для наглядности) с полупериодами, равными простым числам (см. ниже рис.1).

Выбрав любую из синусоид, отметим, что в первой после нуля точке пересечения синусоиды с числовой осью находится простое число, в последующих точках пересечения находятся составные числа, кратные этому простому числу. Простые числа по всей числовой оси выделены черным цветом, составные числа помечаются разноцветными точками – красными, зелеными и синими. Составные числа, отмеченные точками, через которые синусоиды проходят единожды, выделены красным цветом. Но среди точек, обозначающих составные числа, встречаются и такие, через которые проходят две синусоиды (точки выделены зеленым цветом), три синусоиды (синий цвет) и т.д., то есть несколько синусоид. Отмечаем это обстоятельство особо, мы к нему вернемся. Прежде чем провести несложные подсчеты, позволю себе сделать одно важное отступление, содержание которого многим известно, тем не менее, думаю, не всем.











Рис.1

4.1. Введение понятия опорного интервала.
Рассмотрим в качестве примера число 96 и представим его в виде произведения только двух сомножителей. Хочу обратить особое внимание на случай, когда оба сомножителя равны друг другу, т.е. 96=. Величина равна приблизительно 9,8 , т.е. 969,89,8. Понятно, что если уменьшить незначительно первый сомножитель по сравнению с , сохраняя неизменным результат произведения, второй сомножитель автоматически увеличится по сравнению с числом 9,8. Например, 96=9,610 или 969,510,1.

Если попытаться представить любое натуральное число в виде произведения только двух целых сомножителей, то, что касается простых чисел – их разложить на целые сомножители невозможно (напомню, что умножение на единицу нас не интересует). А вот составное число – обязательно можно, часто даже несколькими способами.

В рассматриваемом примере число 96 составное (легко заметить, что оно четное, да еще и делится на 3) и, если попытаться представить его в виде произведения только двух целых чисел, то, понятно, что один из двух целых сомножителей непременно будет меньше 9,8 , а второй – обязательно больше этой величины. Если мы будем уменьшать величину первого сомножителя по отношению к числу последовательно до целых значений 8, 6, 4, 3, 2, принадлежащих интервалу [2;],то увидим, что значение второго целого сомножителя будет возрастать по сравнению с фиксированным значением соответственно до значений 12, 16, 24, 32, 48, входящих в интервал [;96]. Следовательно, для того, чтобы убедиться в том, что число 96 принадлежит к составным числам, вполне достаточно обнаружить хотя бы один целый делитель, на который число 96 делится без остатка, в сравнительно небольшом интервале [2;], и совсем необязательно (это будет нерационально!) искать подобный делитель на гораздо более протяженном отрезке [;96]. То есть, если нет делителя в интервале [2;], то его нет и в интервале [;96]! Но, если число 96 делится нацело на составное число 8, принадлежащее интервалу [2;], то оно обязательно делится без остатка и на простое число 2, которое является простым делителем для составного числа 8, которое еще меньше, чем 8 (вспомним «решето» Эратосфена), и которое также принадлежит интервалу [2;]. Или, если число 96 делится нацело на составное число 6, то оно обязательно делится без остатка на простые числа – либо на 2, либо на 3, (они также являются простыми делителями для числа 6, также меньше, чем 6 и также принадлежат интервалу [2;]). Встречаются составные числа, равные квадрату простого числа, например 49=77 или 121=1111, для них справедливы равенства 7=и 11=, т.е. для чисел 49 и 121 имеется всего лишь один делитель. Но и в этом случае этот делитель содержится в пределах интервала [2;], либо [2;]. Значит, можно более жестко обозначить признак принадлежности числа c к составным числам: необходимо и достаточно найти хотя бы одно простое число в интервале [2;], на которое число c делилось бы без остатка. Если же на указанном интервале нет ни одного простого числа, на которое число c делится без остатка, то в таком случае и само число c является простым числом. В дальнейшем, для краткости, будем называть интервал вида [2;] «опорным интервалом».
4.2. Подсчет составных чисел с помощью синусоид.
Перейдем к подсчету составных чисел в интервале [2;101]. Сначала выделим опорный интервал, заведомо включающий в свои границы все простые числа, которые образуют минимально необходимый набор множителей для образования абсолютно всех составных чисел, входящих в интервал [2;101]. Таковым является интервал [2; ] (на рис.1 участок числовой оси, соответствующий 10,05, выделен оранжевым цветом). Из таблицы простых чисел следует, что простыми числами, меньшими величины , являются соответственно числа 2, 3, 5 и 7. Повторюсь, каждому числу, меньшему, чем 101, соответствует, конечно, меньший опорный интервал. Но каждый из этих опорных интервалов заведомо находится в пределах интервала [2;10,05] и поэтому не может содержать каких-либо других простых чисел, не принадлежащих набору простых чисел 2, 3, 5 и 7. Количество составных чисел, кратных 2, равно =-1= 50-1= 49. Оно равно количеству пересечений синусоиды красного цвета с числовой осью за минусом пересечения на цифре 2, обозначающей простое число 2. Для удобства присвоим этой синусоиде имя «2». Количества чисел, кратных числам 3, 5 и 7, равны соответственно числам =-1=32 (серая синусоида «3»), =-1=19 (фиолетовая синусоида «5») и =-1=13 (желтая синусоида «7»). Для подсчета количества составных чисел можно было бы удовлетвориться суммой полученных результатов, равной +++=49+32+19+13=113, если бы не одно, отмеченное нами ранее особо, обстоятельство. На цифре 6, например, пересекаются одновременно две синусоиды. Следовательно, число 6 сосчитано дважды – с помощью синусоид «2» и «3», т.е. при делении числа 101 и на 2, и на 3. Подобная картина двойного подсчета наблюдается в точках, обозначающих числа 10, 12, 14, 15, 18, 20, 21 и т.д. Если игнорировать этот факт, то в сумме ₊₊₊ дважды будут сосчитаны некоторые из составных чисел, а именно – те, через которые проходят одновременно две синусоиды. Повторюсь, что существуют точки, через которые проходят одновременно даже не две, а три синусоиды (30, 42, 60, 70, 84, 90), в них составные числа просчитываются трижды. А если бы мы в качестве примера выбрали число, гораздо большее, чем 101, то могли бы наблюдать одновременное пересечение в одной точке на числовой оси и четырех, и пяти, и шести и т.д. синусоид. Как уйти от многократного подсчета одних и тех же составных чисел?

Для начала компенсируем двойной подсчет. Для этого рассортируем точки на два вида. Итак, красным цветом обозначены точки, через которые проходит только одна синусоида и которые сосчитаны по одному разу – это один вид точек. Через точки зеленого и синего цвета проходят минимум две синусоиды, и они сосчитаны минимум дважды – это второй вид точек. Пересчитаем количество точек второго вида, а полученный результат вычтем из числа 113.

Для подсчета воспользуемся методом Эратосфена и изобразим рис.2, сохранив расцветку точек с числами такую же, как на рис.1. Цвета точек для нас важны, а вот расцветка синусоид не имеет значения, она используются лишь для удобства, чтобы легче было различать разные синусоиды и не путаться в них. На рис.2 будем проводить линии новых синусоид с полупериодами, теперь уже равными числам, имеющим зеленый цвет. Чем же примечательны эти числа? Начнем с числа 6=23. Как видим, оно кратно сразу двум простым числам, 2 и 3. Поэтому синусоида с полупериодом, равным 6, отмечает все числа, кратные одновременно двум числам 2 и 3: 6, 12, 18, 24, 30,…, 96. Общее количество таких точек в интервале [2;101] равно: ==16 (синусоида «2^.3»). Заметим, теперь нет необходимости из результата деления вычитать единицу, ведь число 6 – первая точка пересечения синусоиды «2^.3» с осью – тоже составное число и оно должно учитываться при подсчете. После первичного «просеивания»

Рис.2

оказывается, что ближайшим к 6 «уцелевшим» зеленым числом является число 10=25. Синусоида «2^.5» с полупериодом, равным 10, отмечает все числа, кратные одновременно двум числам 2 и 5: 10, 20, 30, 40, 50, 60,…, 100. Общее количество таких точек в интервале [2;101] равно: ==10. Далее по порядку, вслед за 6 и 10, такими же числами, уцелевшими после очередного «просеивания», оказываются 14=27, 15=35, 21=37 и 35=57. Причем, ==7, ==6, ==4 и ==2. Теперь мы можем сосчитать количество точек двойного подсчета, которое равно сумме полученных результатов, а именно:

+++++=16+10+7+6+4+2=45.

Что же, количество составных чисел равно 113-45=68? И вновь ответ – нет. Вспомним, что в синих точках рис.1 имел место тройной подсчет, а мы его пока и не брались компенсировать. Следовательно, в результате 113-45=68 пока присутствует ошибка – не учтен тройной подсчет одних и тех же составных чисел. Более того, в каждой из этих же синих точек, только уже на рис.2, пересекаются по три «компенсационные» синусоиды, что явно сулит необходимость новой компенсации, причем теперь уже придется компенсировать результат предыдущей компенсации двойного подсчета, т.е. вносить поправку в число 45. Примечательно, что потребность в новых компенсациях возникает в тех же самых синих точках на рис.1 и рис.2.

Однако и эти ошибки устраняются аналогичным способом. Компенсируем тройной подсчет. На рис.3 с помощью метода Эратосфена можно провести только три синусоиды, имеющие полупериоды, равные синим числам соответственно 30=235, 42=237 и 70=257 (синусоиды «2^.3^.5», «2^.3^.7»и «2^.5^.7»). В чем же особенность точек 30(60, 90), 42(84) и 70, которые были окрашены в синий цвет еще на рис.1? Поскольку на рис.1 через них проходили сразу три синусоиды, они являлись точками тройного подсчета, т.е. в них трижды учитывалось одно и то же составное число. Следовательно, корректировать подсчет в этих точках необходимо не на один раз лишнего подсчета, как в зеленых точках, а на два лишних раза. И все было бы замечательно, если бы на рис.2 в синих точках собирались бы по две «компенсационные» синусоиды – тогда бы число 45 в результате 113-45=68 действительно было бы истинным числом компенсации лишних подсчетов одних и тех же составных чисел.








Рис.3

Но, на рис.2 через эти же самые синие точки прошли не две, а три «компенсационные» синусоиды. Компенсация в синих точках получилась чрезмерной, с излишком на один раз. Обратите внимание, все синие числа на рис.1 просчитываются по три раза, и на рис.2 они же просчитываются опять по три раза. Т.е. в результате 113-45=68 синие точки вообще не учтены! Зато на рис.3 новые синусоиды, относящиеся к следующему этапу компенсации, пересекают синие числа каждая сама по себе – один раз, ни в какой точке синего цвета не пересекаются две (или более) новые компенсационные синусоиды. Т.о., сосчитав синие числа и прибавив это количество к промежуточному результату 113–45=68, мы избавляемся от чрезмерной компенсации в синих точках, имевшей место на предыдущем этапе компенсации, и, наконец-то, получаем желанный ответ. Подсчитываем синие числа уже привычным для нас способом: ==3, ==2, ==1, ++=3+2+1=6. Количество составных чисел в интервале [2;101] равно: 113-45+6=74. Следовательно, количество простых чисел на указанном интервале равно 100-74=26, это означает, что простое число 101 имеет номер 26, что и подтверждается таблицей простых чисел.

Естественны сомнения в универсальности и точности столь «запутанного», на первый взгляд, предлагаемого метода (оказывается, иногда совсем непросто сосчитать до трех!). Т.е. полученный результат может быть простым совпадением, и нет гарантии, что в дальнейшем, в некоторых частных случаях, при больших значениях простых чисел и больших количествах синусоид, мы не ошибемся в подсчетах количества составных чисел. До сих пор, в принципе, преследовалась цель иллюстрации метода, с помощью которого нам предстоит вывести алгоритм, для знакомства с ним. Попытаемся доказать безошибочность предлагаемого метода для подсчета количества составных и простых чисел в любом числовом интервале.