Исследование путей улучшения алгоритма поиска простых чисел

Пузиков Р.Ю.
© 2006

Единственным, на сегодняшний день надёжным способом найти новые простые числа является алгоритм Эратосфена. Он подразумевает, что с числом, которое мы проверяем на «простоту» необходимо провести ряд проверок на делимость с простыми числами от двух(трёх) и вплоть до корня из проверяемого числа. Алгоритм Эратосфена легко реализуем, но его главная проблема в относительной неспешности. Когда проверяются достаточно большие числа, то требуется провести много проверок на деление. Которые и сами по себе не мгновенно выполняются, так и требуют много действий с оперативной памятью. Впрочем, я думаю, есть возможность его несколько ускорить достаточно простым способом:

1. Определяем зону поиска N – например надо найти простые числа в промежутке от десяти миллионов до десяти миллиардов. В первую очередь важна верхняя граница. Что бы проверить число близкое к 10 миллиардам надо выполнить проверку на делимость с простыми числами вплоть до корня из верхней границы, то есть до ста тысяч.
2. Подготавливаем или берём таблицу простых чисел от 3 и до ста тысяч. И формируем ряд проверочных чисел (Х), представляющих собой произведение простых чисел, идущих подряд. Например:
   Х1=3*7*11*13*17*19*23*29*31*…*101
   Х2=103*107*109*113*127*131*…*199
   И так далее, вплоть до ста тысяч.
   При формировании проверочных чисел следует придерживаться лишь их некой, заранее заданной длины, например 1024 бита. В результате в одно проверочное число Х «войдёт» не менее 60 простых чисел, даже пятизначных. И в итоге получим около 200 проверочных чисел, так как простых чисел до 100.000 около 12 тысяч.
3. Берём проверяемое число из зоны поиска N, обозначим его как «р» и ищем наибольший общий делитель с проверочными числами.
   НОД (р, Х1), НОД (р, Х2)
   Если такой делитель имеется, то тогда «р» не является простым числом и надо проверять следующее число из зоны поиска. Ну а если общего делителя нет, то тогда ищем НОД со следующим проверочным числом и так пока не дойдём до последнего проверочного числа. Пройдя все проверки (не более 200) и не имея общих делителей ни с одним проверочным числом «Х», можно признать проверяемое число «р» простым.

Но имеется несколько моментов, которые обязательно нужно учесть, что бы данный способ стал эффективным:

1. Надо искать возможные делители только до корня из «р», а стало быть использовать только те проверочные числа «Х», которые перекрывают эту зону. Или разбить зону поиска N, на несколько участков, соответствующих различным «Х» (то есть по квадратам их наибольших составляющих).
2. Поиск НОД с первым проверочным числом «Х» необходимо доводить до конца, но вот со следующими проверочными числами это необязательно. Так как мы точно знаем, из каких простых чисел образуются проверочные числа «Х», и искать НОД среди чисел, меньших, чем наименьшая составляющая «Х» просто бессмысленно.
3. Последнее замечание – поскольку нужен быстрый алгоритм поиска, то обязательно нужно учесть, что большинство чисел в зоне поиска будут делиться на малые числа, например 3, 7,11, 13… и потому целесообразней будет сначала устроить простую проверку на делимость по этим числам, а уже потом использовать проверочные числа «Х». По тем же причинам, возможно, не окажется необходимым сразу использовать большой размер у проверочных чисел «Х», а использовать относительно небольшой размер – например 64 бита (в которые тоже «поместится» немало 2-3-значных чисел, а они будут встречаться не в пример чаще 4-5-значных)

Впрочем, учёного учить – только портить, если эту идею вы сочтёте целесообразной, то и сами придумаете, как алгоритм сделать лучше и быстрей.

Теперь хочу рассказать о своём маленьком исследовании простых чисел.

Я попытался их графически расположить на плоскости. В качестве основы взяты как сами простые числа, так и промежутки между ними – сколько целых чисел помещается между двумя соседними простыми – записано через тире и именно на них надо обращать внимание.

2 – 0
3 – 1
5 – 1, 7 – 3, 11 – 1
13 – 3, 17 – 1, 19 – 3, 23 – 5, 29 – 1, 31 – 5, 37 – 3, 41 – 1, 43 – 3
47 – 5
53 – 5, 59 – 1, 61 – 5
67 – 3
71 – 1
73 – 5,79 – 3, 83 – 5
89 – 7
97 – 3, 101 – 1, 103 – 3, 107 – 1, 109 – 3
113 – 13
127 – 3
131 – 5
137–1,139–9,149–1,151–5,157–5,163–3,167–5,173–5,179–1,181–9,191–1
193 - 3
197 – 1
199 – 11, 211 – 11
223 – 3, 227 –1, 229 –3
233 – 5
239 – 1
241 – 9
251 – 5, 257 – 5, 263 – 5
269 – 1
271 – 5
277 – 3
281 – 1
283 – 9
293 – 13, 307 – 3, 311 – 1, 313 – 3, 317 – 13
331 – 5
337 – 9
347 – 1
349 – 3
353 – 5, 359 – 7, 367 – 5
373 – 5, 379 – 3, 383 – 5
389 – 7, 397 – 3, 401 – 7
431 – 1
433 – 5,439 – 3, 443 – 5
449 – 7
457 – 3,461 – 1, 463 – 3
467 – 11
479 – 7, 487 – 3, 491 – 7
499 – 3
503 – 5
509 – 11
521 – 1
523 – 17
541 – 5, 547 – 9, 557 – 5
563 – 5, 569 – 1, 571 – 5
577 – 9
587 – 5, 593 – 5, 599 – 1, 601 – 5, 607 – 5
613 – 3
617 – 1
619 – 11
631 – 9
641 – 1
643 – 3
647 – 5, 653 – 5
659 – 1
661 – 11
673 – 5, 677 – 5, 683 – 7, 691 – 9, 701 – 7, 709 – 9, 719 – 7, 727 – 5, 733 – 5
739 – 3
743 – 7
751 – 5
757 – 3, 761 – 7, 769 – 3
773 – 13
787 – 9
797 – 11
809 – 1
811 – 9, 821 – 1, 823 – 3, 827 – 1, 829 – 9
839 – 13, 853 – 3, 857 – 1, 859 – 3, 863 – 13
877 – 3, 881 – 1, 883 – 3
887 – 9
907 – 3, 911 – 7, 919 – 9, 929 – 7, 937 – 3
941 – 5, 947 – 5
953 – 13
967 – 3
971 – 5
977 – 5, 983 – 7, 991 – 5
997 – 11

Как видно, числа тут разбиваются на группы по симметрии, есть зоны регулярные и зоны нерегулярные (по крайней мере, на первый взгляд – попробуем убрать, например, число 71 и перерисуем ближайший к нему кусок таблицы по этим же правилам, и учтите – что это далеко не самый показательный пример!)

47 – 5, 53 – 5, 59 – 1, 61 – 5, 67 – 5 ₍₇₃₎,

то есть появилась ещё одна группа симметрии.

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

И потому я пришёл к такому предположению (возможно и не верному), что единой закономерности, единой формулы, которая будет описывать всё множество простых чисел сразу, по всей видимости, не существует. А если это и возможно описать простые числа, то только через множество маленьких зависимостей, маленьких формул описывающих несколько простых чисел, причем все элементы этого множества завязаны друг на друга, одно зависит от предыдущего и является определяющим для «последователей».

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

Надеюсь, она будет интересной и для читателей.