Простые числа

Студент на экзамене:
«Чтобы составить таблицу простых чисел,
нужно трясти решето.»
Преподаватель: «Сколько раз?»
Студент: «Ну, пока не вытрясется все лишнее.»

Мехматовский фольклор

Когда великому русскому механику и математику-прикладнику
Алексею Николаевичу Крылову (1863 – 1945) сказали,
что другой великий, но в то время совсем молодой русский математик
Иван Матвеевич Виноградов (1891 – 1983)
получил чрезвычайно значительные результаты
в аддитивной теории простых чисел и
претендует на место академика, Крылов заметил:
«А меня в гимназии учили,
что простые числа надо не складывать, а перемножать!»

Из истории простых чисел



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

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 и т.д.

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

Впервые на простые числа обратили внимание древние греки. Наибольших успехов в их исследовании добился Эратосфен (276 – 194 гг. до н.э.), который предложил решето, впоследствии названное его именем, для отыскания простых чисел.
В решете Эратосфена вычёркиваются столбцы начинающиеся на 4,6,8,9 (они обозначены вишнёвым цветом), затем таблица пересекается диагоналями начинающимися с чисел оканчивающихся на 5 (синий цвет). Затем диагоналями в противоположном направлении с числа 14 и шагом 42 (56, 98, 140)(синий цвет). Оставшиеся после этого числа представляют собой простые числа (они обозначены красным цветом).
Но уже на числах 121(11*11), 143(11*13), 169(13*13) решето пропускает составные числа. Таким образом, не смотря на элегантность и простоту решения решето Эратосфена не позволяет получить фактический ряд простых чисел. Ошибку Эратосфена повторили в последствии многие исследователи ряда простых чисел, предлагая те или иные формы решета, но каждый раз вместе с простыми числами сквозь его сито проскальзывали числа составные.

Для практических целей ряд простых чисел получают путём последовательного деления соответствующего числа натурального ряда на члены массива простого ряда отстоящего слева от корня квадратного этого числа. Например, для определения простых чисел в интервале от 10 до 100 необходимо последовательно делить искомое число на все простые числа, стоящие  перед 10. Берём первое нечётное число, стоящее, например за 20: 21 и делим его на члены ряда 3, 5, 7. Находим его делители 3 и 7, следовательно, это число составное. Для числа 23 нет соответствующего множителя, следовательно, это число простое и т.д. Так последовательно создаётся таблица простых чисел.

В настоящее время наиболее полной таблицей простых чисел, является таблица Д.Н. Лехмера (1905 – 1991), рассчитанная до значения 10 010 323. Следующими простыми числами, вероятно могут быть 10 010 333, 10 010 339, 10 010 347.

Интерес к простым числам проявлял Ферма (1601 – 1665), который предложил для их вычисления формулу:

Fn = 2^( 2^n) + 1
для n = 0, 1, 2, 3, 4…

F0 = 2^(2^0) + 1 = 3
F1 = 2^(2^1) + 1 = 5
F2 = 2^(2^2) + 1 = 17
F3 = 2^(2^3) + 1 = 257
F4 = 2^(2^4) + 1 = 65 537

Дальнейшую проверку своей формулы Ферма не проводил.

F5 = 2^(2^5) + 1 = 4 294 967 297

Но это число уже не является простым:

F5 = 4 294 967 297 = 641 * 6700417

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

Аналогичная попытка была предпринята Мерсенном (1588 – 1648), который предложил для отыскания простых чисел довольно простую формулу:

Mn = 2^n – 1

где n – соответствующий член ряда простых чисел (2, 3, 5, 7…)
Но уже для n=11 число Мерсенна не является простым:

M11 = 2^11 – 1 = 2047 = 23 * 89

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

Для предварительной оценки потенциального кандидата на простое число необходимо вычислить его внутреннюю сумму:

10 010 327 // 1 + 1 + 3 + 2 + 7 = 14 // 1 + 4 = 5
10 010 329 // 1 + 1 + 3 + 2 + 9 = 16 // 1 + 6 = 7
10 010 331 // 1 + 1 + 3 + 3 + 1 = 9
10 010 333 // 1 + 1 + 3 + 3 + 3 = 11 // 1 + 1 = 2
10 010 339 // 1 + 1 + 3 + 3 + 9 = 17 // 1 + 7 = 8
10 010 347 // 1 + 1 + 3 + 4 + 7 = 16 // 1 + 6 = 7

Из рассмотренных кандидатов одно число точно не является простым:

10 010 331 = 3*3336777

Остальные кандидаты удовлетворяют условию не кратности внутренней суммы трём. Их проверка на возможность быть простым числом проводится путём отыскания двух чисел, из которых может состоять рассматриваемый кандидат:

10 010 327 = 79 * 126713
10 010 329 = 7 * 1430047

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

Отыскание простых чисел может осуществляться решением обратной задачи, т.е. нахождением гармоничных рядов составных чисел и вычитанием их из натурального ряда. В качестве примера можно привести зависимость:

ni = n0 + i*d

где
ni – соответствующий член ряда
n0 – первый член ряда
i – число натурального ряда: 0, 1, 2, 3, 4, 5 …
d - эмпирический коэффициент.

Для первых пяти рядов
n0 (4, 7, 17, 19, 27 …)
d (3, 5, 7, 13, 11 …)

n0 = 4; d = 3
ni (4, 7, 10, 13, 16, 19, 22, 25, 28, 31 …)

Аналогично находятся значения других рядов.
Для вычисления простых чисел полученные ряды необходимо преобразовать к нечётному ряду:

N0 = 2*n0 + 1
D = 2*d

n0 – первый член эмпирического ряда;
d - эмпирический коэффициент.

Суммируя полученные ряды (1 – 5) получаем ряд:

9, 15, 21, 25, 27, 33, 35, 39, 45, 49 …

Вычитаем его из нечётного натурального ряда:

9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45 …

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

11, 13, 17, 19, 23, 31, 37, 41, 43, 47 …

Для определения простых чисел в выборках натуральных чисел более 300, необходимо знание характеристик экспериментальных рядов более 5.
Для отыскания простых чисел в интервале от 1 до 1000 необходимо знание параметров 9 экспериментальных рядов, для интервала 1001 до 2000 – 14 и т.д.