Alexander_IK Oct 18 2019 at 12:49

Формула расчёта простых чисел и оптимизация перебора делителей

3 min

14K

Приветствую! Решил на досуге исследовать задачу поиска простых чисел. Тема обширная и интересная. Хочу поделиться парой соображений по ней, которые пришли в голову. Поиск в сети интернет подобных не выявил, указав на их оригинальность.

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

Для некоторой последовательности чисел $(x_{m})={x_{1},x_{2},x_{3},...x_{max}}$ введём оператор обнаружения первого числа, равного a:

$\mathbf{Dt_{a}}(x_{m}):=\left\{\begin{matrix}m \ \mathbf{if} \ \exists \ m: \forall \, k<m \ x_{k}\neq a \ \mathbf{and} \ x_{m}=a \\ 0\ \mathbf{otherwise}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{matrix}\right.$

Все простые числа, начиная с 5-ки, можно вычислить по формуле:

$P_{n}=P_{n-1}+2 \mathbf{Dt_{0}^{i}}(\mathbf{Dt_{0}^{j}}((P_{n-1}+2i) \, mod \, P_{j+1})), \ \ \ \forall \, n \geqslant 3 \\ \forall \, i_{max}\geqslant \max\frac{P_{\alpha}-P_{\alpha -1}}{2}+10 \,, \ \ 2 \leqslant\alpha \leqslant n-1; \ \ j_{max}=\pi (\sqrt{P_{n-1}+2i})-1$

Оператор $\mathbf{Dt_{0}^{j}}$ перебирает по $inline$ остатки от деления каждого числа-кандидата на простоту с $inline$ -м номером $(P_{n-1}+2i)$ на уже найденные простые числа в диапазоне до $P_{j_{max}+1}$ . Числа-кандидаты выбираются по порядку из множества нечётных чисел, больших предыдущего простого числа $P_{n-1}$ . $\pi (\sqrt{P_{n-1}+2i})$ — это пи-функция, показывающая количество простых чисел $\leqslant\sqrt{P_{n-1}+2i}$ .
Оператор $\mathbf{Dt_{0}^{i}}$ перебирает по $inline$ выходные значения оператора $\mathbf{Dt_{0}^{j}}$ до тех пор, пока не обнаружит 0. Так как ряд простых чисел бесконечен, это рано или поздно произойдёт. На выходе оператора $\mathbf{Dt_{0}^{i}}$ , таким образом, всегда будет некоторый номер $inline$ . Нижняя граница $i_{max}$ определяется максимальной разностью соседних простых чисел, меньших искомого. Прирост такой разности происходит логарифмически. На графике ниже представлены зависимости максимального и среднего прироста $\Delta P_{\alpha }$ от n для первых 100000 простых чисел. Выборка максимального значения и усреднение проводились для каждой тысячи чисел.

Максимальный прирост разности простых чисел $\delta _{max}(\Delta P_{\alpha })$ к предыдущему максимальному значению $max(\Delta P_{\alpha })$ равен 20 (для разности простых чисел 31397-31469=72 по отношению к разности 25523-25471=52). Он находится в области, где производная логарифма огибающей $\Delta P_{\alpha }$ ещё достаточно велика, а простые числа уже не слишком малы. Исходя из этого значения получено условие для $i_{max}$ . График $\delta _{max}(\Delta P_{\alpha })$ для первых 50000 простых чисел дан ниже. Значения вычислялись для каждой тысячи.

Виден пик на значении 20. С увеличением n график уходит в минус, показывая уменьшение скорости прироста больших простых чисел.

Второе соображение касается оптимизации вычисления последовательности простых чисел.
Алгоритм, заложенный в формуле выше- это улучшенный метод перебора делителей. Улучшения заключаются в исключении из рассмотрения чётных чисел и проверке делимости только на простые числа, меньшие кв. корней чисел-кандидатов. Самая сложная часть алгоритма- это вычисление множества функций взятия остатка mod. Уменьшить сложность можно путём оптимизации этой функции. Однако, есть ещё более эффективный способ. Пусть $(r_{j+1}^{n-1})={r_{2},r_{3},...r_{\pi (\sqrt{P_{n-1}})}}$ — это последовательность остатков от деления последнего найденного простого числа на простые числа от 3-ки до корня из него. Будем составлять последовательности вида

$(r_{i,j+1}^{n})={(r_{2}+2i) \, mod \, P_2,(r_{3}+2i) \, mod \, P_3,... \\ (r_{\pi (\sqrt{P_{n-1}})}+2i) \, mod \, P_{\pi (\sqrt{P_{n-1}})},(P_{n-1}+2i) \, mod \, P_{\pi (\sqrt{P_{n-1}+2i})}}$

по порядку, начиная с $inline$ . Последний член вычисляется в случае, если $\pi (\sqrt{P_{n-1}+2i}) \neq \pi (\sqrt{P_{n-1}})$ . Когда на некотором шаге вычисления остаток $r_{i,j+1}^{n}$ становится равным 0, выполняется переход к следующей последовательности. Это делается до тех пор, пока не будет обнаружено i, при котором все остатки ненулевые. Это означает обнаружение очередного простого числа. Последовательность $(r_{j+1}^{n})$ при этом необходимо сохранить до обнаружения следующего простого числа. Рекуррентная формула расчёта простых чисел таким способом преобразуется к виду:

$P_{n}=P_{n-1}+2 \mathbf{Dt_{0}^{i}}(\mathbf{Dt_{0}^{j}}(r_{i,j+1}^{n})), \ \ \ \forall \, n \geqslant 3$

В представленном алгоритме операция mod облегчена: делимые всего в $(r_{j+1}+2i)/P_{j+1}$ раз больше делителей. Исключение составляют только случаи появления новых простых делителей. В памяти ЭВМ при реализации алгоритма необходимо хранить массив простых чисел до корня из искомого, а также переменный массив остатков. Сложность алгоритма в общем смысле (объём работы) может быть меньше, чем у других известных методов. Самые сложные операции в нём- это извлечение квадратного корня, вычисление остатков и умножение. Корень можно извлекать с точностью до целой части. Для получения остатков можно использовать эффективный алгоритм, основанный на общем правиле делимости. Умножение используется только на 2-ку относительно малых чисел i. Временную сложность алгоритма можно уменьшить, распределив работу по значениям i. Полученное таким путём сегментированное сито должно работать быстрее на многопоточных вычислителях. Однако, выполняемая работа будет больше ввиду увеличения делимых. Ещё к алгоритму можно «прикрутить» колёсную факторизацию. При оптимальном размере колёс это может уменьшить сложность в некотором диапазоне n — до тех пор, пока аппаратные «дебри» не затормозят его.

Возможно, кому-то мои соображения пригодятся.

Tags:

Hubs: