Алгоритм определения простых чисел

[Леонид Вайсруб]

Всякое целое число $p \ge 5$ представимо в одном из следующих видов
$ 6n - 1, 6n, 6n + 1, 6n + 2, 6n + 3, 6n + 4 $ при некотором $ n \in \mathbb N $ (это число $ n $ будем обозначать $n_{p}$). Очевидно, что если число $p \ge 5$ - простое, то либо $p = 6n_{p} - 1$, либо $p = 6n_{p} + 1$ (первый случай
характеризуется условием "$p + 1$ делится на 6", второй - условием
"$p - 1$ делится на 6").
Назовем узлами четные числа $ 6n, n = 1, 2, 3, \ldots $, а число $ n $ номером узла. Далее, узел с номером $ n = s $, для которого рядом стоящие с ним числа $ 6s - 1$ и $ 6s + 1 $ являются простыми числами (числа близнецы), назовем полным (или двусторонним, полноценным, полновесным) узлом, а узел, для которого одно из двух чисел $ 6s - 1$ или $ 6s + 1 $ является простым, назовем односторонним (соответственно, левосторонним, если число $ 6s - 1 $ является простым, а число $ 6s + 1 $ составным, и правосторонним, если число $ 6s + 1 $ является простым, а число $ 6s - 1 $ составным). Узел, для которого рядом стоящие с ним числа $ 6s - 1 $ и $ 6s + 1 $ являются составными, назовем пустым узлом. В каждой шестерке чисел от $ 6n - 1 $ до $ 6n + 4 $ включительно, $ n = 1, 2, 3, \ldots $ только два нечетных числа $ 6s - 1$ и $ 6s + 1 $ могут быть простыми числами (так как числа $ 6n, 6n + 2, 6n + 4 $ - четные и число $ 6n + 3 = 3(2n + 1) $ составное, делится на 3).
Выясним, при каких условиях эти числа являются простыми.

Первый случай: $ p = 6n_{p} - 1.$ Если число $ p $ -
составное, то оно представимо в виде $p = (6u - 1)(6v + 1)$ ($ 6n + 3 $ не может быть множителем, так как $p + 1$ делится на 6). Если
таких представлений несколько, то берется любое из них (это замечание ниже повторяться
не будет). Имеем $6n_{p} - 1 = (6u - 1)(6v + 1)$, откуда

$$n_{p} = 6uv + u - v, ~~~~~~~~~~~~~ (1)$$

где $ u, v \in \mathbb N $. Выясним, при каких условиях число $n_{p} $, может быть представлено в такой форме (другими словами, при каких
условиях диофантово уравнение (1) имеет решение $(u, v, n_{p})$, в котором
$ u, v \in \mathbb N $.).

I. Число $n_{p} $ - четное. В этом случае числа $u$ и
$v$ либо оба четные, либо оба нечетные.

1) $u \le v$. В этом случае $ v = u + 2k (k = 0, 1, 2, \ldots)$ получаем $ n_{p} = 6uv + u - v = 6u(u + 2k) + u - (u + 2k) = 6u^{2} + 12uk - 2k $, откуда

$$ k = \frac{n_{p} - 6u^{2}}{2(6u - 1)}. ~~~~~~~~ (2)$$

Так как $ k \ge 0 $, то $ n_{p} - 6u^{2} \ge 0 $, откуда следует, что

$$ u \le \sqrt{\frac{n_{p}}{6}}. ~~~~~~~~~~~~ (3)$$

Вывод: если для какого-нибудь значения $ u $ от 1 до
$ \left[\sqrt{\frac{n_{p}}{6}} \right] $ ($ \left[ x \right] $ - целая часть числа $ x $) число $ k $, вычисленное по формуле (2),
окажется целым, то число $n_{p} $ может быть
представлено в виде (1) и, значит, число $ p $ -
составное. В противном случае число $ p $ - простое.

2) $ u > v $ . В этом случае $ u = v + 2k (k \in \mathbb) $ и получаем $ n_{p} = 6uv + u - v = 6(v + 2k)v + v + 2k - v = 6v^{2} + 12vk + 2k $, откуда

$$ k = \frac{n_{p} - 6v^{2}}{2(6v + 1)}. ~~~~~~~~~ (4)$$

Так как $ k > 0 $, то $ n_{p} - 6v^{2} > 0 $, откуда следует, что

$$ v < \sqrt{\frac{n_{p}}{6}}. ~~~~~~~~~ (5)$$

Вывод: если для какого-нибудь значения $ v $ от 1 до
$ \left[\sqrt{\frac{n_{p}}{6}} \right]$ число $ k $, вычисленное по формуле (4), окажется целым, то
число $ n_{p} $ может быть представлено в виде (1)
и, значит, число $ p $ - составное. В противном
случае число $ p $ - простое.

II. Число $ n_{p} $ - нечетное. В этом случае одно из чисел $ u, v $ - четное, другое - нечетное.

1) $ u < v $. В этом случае $v = u + 2k + 1 (k = 0, 1, 2, \ldots) $ и получаем $ n_{p} = 6uv + u - v = 6u(u + 2k + 1) + u - (u + 2k + 1) = 6u^{2} + 6u - 1 + 2k(6u - 1)$, откуда

$$ k = \frac{n_{p} - 6u^{2} - 6u + 1}{2(6u - 1)}. ~~~~~~~~~~~~ (6)$$

Так как $ k \ge 0 $, то $ n_{p} - 6u^{2} - 6u + 1 \ge 0 $, откуда следует, что

$$ u \le \frac{\sqrt{6n_{p} + 15} - 3}{6}. ~~~~~~~~ (7)$$

Вывод: если для какого-нибудь значения $ u $ от 1
до $ \left[\frac{\sqrt{6n_{p} + 15} - 3}{6} \right] $ число $ k $, вычисленное по формуле (6),
окажется целым, то число $ n_{p} $ может быть
представлено в виде (1) и, значит, число $ p $ -
составное. В противном случае число $ p $ -
простое.

2) $ u > v $. В этом случае $ u = v + 2k + 1 (k = 0, 1, 2, \ldots) $ и получаем $ n_{p} = 6uv + u - v = 6(v + 2k + 1)v + v + 2k + 1 - v = 6v^{2} + 6v + 1 + 2k(6v + 1) $, откуда

$$ k = \frac{n_{p} - 6v^{2} - 6v - 1}{2(6v + 1)}. ~~~~~~~ (8)$$

Так как $ k \ge 0 $, то $ n_{p} - 6v^{2} - 6v - 1 \ge 0 $, откуда следует, что
$ v \le \frac{\sqrt{6n_{p} + 3} - 3}{6}. ~~~~~~~~~ (9)$

Вывод: если для какого-нибудь значения $ v $ от 1
до $ \left[\frac{\sqrt{6n_{p} + 3} - 3}{6} \right] $ число $ k $, вычисленное по формуле (8),
окажется целым, то число $ n_{p} $ может быть
представлено в виде (1) и, значит, число $ p $ -
составное. В противном случае число $ p $ -
простое.

Второй случай: $ p = 6n_{p} + 1.$

Если число $ p $ - составное, то оно представимо в
виде $ p = (6u + 1)(6v + 1) $ или $ p = (6u - 1)(6v - 1) $ ($ 6n + 3 $ не может быть
множителем, так как $ p - 1 $ делится на 6). Имеем
$ 6n_{p} + 1 = (6u + 1)(6v + 1) $ или $ 6n_{p} + 1 = (6u - 1)(6v - 1) $, откуда

$ n_{p} = 6uv + u + v $, (10)

или

$ n_{p} = 6uv - u - v $, (11)

где $ u, v \in \mathbb N $. Очевидно, что можно
считать, что в этих уравнениях $ u \le v $.
Выясним, при каких условиях число $ n_{p} $ может
быть представлено в виде (10) или (11) (другими словами, при каких
условиях одно из диофантовых уравнений (10), (11) имеет решение
$ (u, v, n_{p}) $, в котором $ u, v \in \mathbb N $).

I. Число $ n_{p} $ - четное. В этом случае числа $ u $ и
$ v $ либо оба четные, либо оба нечетные. Следовательно, $ v = u + 2k (k = 0, 1, 2, \ldots) $.

1) Рассмотрим уравнение (10). Имеем $ n_{p} = 6uv + u + v = 6u(u + 2k) + u + (u + 2k) = 6u^{2} + 2u + 2k(6u + 1) $,
откуда

$$ k = \frac{n_{p} - 6u^{2} - 6u}{2(6u + 1)}.~~~~~~~~~~~ (12)$$

Так как $ k \ge 0 $, то $ n_{p} - 6u^{2} - 2u \ge 0 $, откуда следует, что

$$ u \le \frac{\sqrt{6n_{p} + 1} - 1}{6}. ~~~~~~~ (13)$$

Вывод: если для какого-нибудь значения $ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 1} - 1}{6} \right] $ число $ k $,
вычисленное по формуле (12), окажется целым, то число $ n_{p} $ может
быть представлено в виде (10) и, значит, число $ p $ - составное.

2) Рассмотрим уравнение (11). Имеем $ n_{p} = 6uv - u - v = 6u(u + 2k) - u - (u + 2k) = 6u^{2} - 2u + 2k(6u - 1) $,
откуда

$$ k = \frac{n_{p} - 6u^{2} + 2u}{2(6u - 1)}. ~~~~~~~~~~ (14)$$

Так как $ k \ge 0 $, то $ n_{p} - 6u^{2} + 2u \ge 0 $, откуда следует, что

$$ u \le \frac{\sqrt{6n_{p} + 1} + 1}{6}. ~~~~~~~~~ (15)$$

Вывод: если для какого-нибудь значения $ u $ от 1
до $ \left[\frac{\sqrt{6n_{p} + 1} + 1}{6} \right] $ число $ k $, вычисленное по формуле (14),
окажется целым, то число $ n_{p} $ может быть
представлено в виде (11) и, значит, число $ p $ -
составное.

Общий вывод в случае I : если для какого-нибудь значения $ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 1} - 1}{6} \right] $ число $ k $,
вычисленное по формуле (12), окажется целым или для какого-нибудь значения $ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 1} + 1}{6} \right] $ число
$ k $, вычисленное по формуле (14), окажется целым, то число $ p $ - составное. В противном случае число $ p $ - простое.

II. Число $ n_{p} $ - нечетное. В этом случае одно из чисел $ u, v $ - четное, другое - нечетное. Следовательно, $ v = u + 2k + 1 (k = 0, 1, 2, \ldots) $.

1) Рассмотрим уравнение (10). Имеем $ n_{p} = 6uv + u + v = 6u(u + 2k + 1) + u + u + 2k + 1 = 6u^{2} + 8u + 1 + 2k(6u + 1) $, откуда

$$ k = \frac{n_{p} - 6u^{2} - 8u - 1}{2(6u + 1)}. ~~~~~~~~ (16) $$

Так как $ k \ge 0 $, то $ n_{p} - 6u^{2} - 8u - 1 \ge 0 $, откуда следует, что

$$ u \le \frac{\sqrt{6n_{p} + 10} - 4}{6}. ~~~~~~~ (17)$$

Вывод: если для какого-нибудь значения $ u $ от 1
до $ \left[\frac{\sqrt{6n_{p} + 10} - 4}{6} \right] $ число $ k $, вычисленное по формуле (16),
окажется целым, то число $ n_{p} $ может быть
представлено в виде (10) и, значит, число $ p $ -
составное.

2) Рассмотрим уравнение (11). Имеем $ n_{p} = 6uv - u - v = 6u(u + 2k + 1) - u - (u + 2k + 1) = 6u^{2} + 4u - 1 + 2k(6u - 1) $, откуда

$$ k = \frac{n_{p} - 6u^{2} - 4u + 1}{2(6u - 1)}. ~~~~~~ (18)$$

Так как $ k \ge 0 $, то $ n_{p} - 6u^{2} - 4u + 1 \ge 0 $, откуда следует, что

$$ u \le \frac{\sqrt{6n_{p} + 10} - 2}{6} $$

. Вывод: если для
какого-нибудь значения $ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 10} - 2}{6} \right] $ число
$ k $, вычисленное по формуле (18), окажется целым,
то число $ n_{p} $ может быть представлено в виде
(11) и, значит, число $ p $ - составное.

Общий вывод в случае II : если для какого-нибудь значения $ u $ от 1 до
$ \left[\frac{\sqrt{6n_{p} + 10} - 4}{6} \right] $ число $ k $, вычисленное по формуле (16), окажется целым или для какого-нибудь значения
$ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 10} - 2}{6} \right] $ число $ k $, вычисленное по формуле (18), окажется целым, то
число $ p $ - составное. В противном случае число $ p $ -
простое.



Таким образом, для решения задачи "является ли данное число $ p \ge 5 $
простым?" можно предложить следующий алгоритм.

1) Находим остаток от деления числа $ p $ на 6. Если он $ \ne 1 $ и $ \ne 5 $, то число $ p $ не является простым.

2) Если $ p = 6n_{p} - 1 $ (остаток от деления $ p $ на 6
равен 5), число $ n_{p} $ - четное и для некоторого значения $ u $ от 1 до $ \left[{\sqrt{\frac{n_{p}}{6}} \right] $ хотя бы одно из
чисел $ k = \frac{n_{p} - 6u^{2}} {2(6u \pm 1)} $ является целым, то
число $ p $ не является простым. Если же все эти числа $ k $ не являются целыми, то число $ p $ - простое.

3) Если $ p = 6n_{p} - 1$ (остаток от деления
$ p $ на 6 равен 5), число $ n_{p} $
- нечетное и для некоторого значения $ u $ от 1 до
$ \left[\frac{\sqrt{6n_{p} + 15} - 3}{6} \right] $
хотя бы одно из чисел $ k = \frac{n_{p} - 6u^{2} - 6u + 1} {2(6u - 1)} $ является целым или для некоторого значения
$ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 3} - 3}{6} \right] $ хотя бы одно из чисел $ k = \frac{n_{p} - 6u^{2} - 6u - 1} {2(6u + 1)} $ является
целым, то число $ p $ не является простым. Если же
все эти числа $ k $ не являются целыми, то число
$ p $ - простое.

4) Если $ p = 6n_{p} + 1$, число $ n_{p} $ - четное и для
некоторого значе-ния $ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 1} - 1}{6} \right] $ хотя бы одно из чисел $ k = \frac{n_{p} - 6u^{2} - 2u}{2(6u + 1)} $ является целым или для некоторого значения $ u $
от 1 до $ \left[\frac{\sqrt{6n_{p} + 1} + 1}{6} \right] $ хотя бы одно из
чисел $ k = \frac{n_{p} - 6u^{2} + 2u}{2(6u - 1)} $ является целым, то
число $ p $ не является простым. Если же все эти числа $ k $ не являются целыми, то число $ p $ - простое.

5) Если $ p = 6n_{p} + 1$, число $ n_{p} $ - нечетное и для некоторого значения $ u $
от 1 до $ \left[\frac{\sqrt{6n_{p} + 10} - 4}{6} \right] $ хотя бы одно из чисел $ k = \frac{n_{p} - 6u^{2} - 8u - 1} {2(6u + 1)} $ является целым или для некоторого
значения $ u $ от 1 до $ \left[\frac{\sqrt{6n_{p} + 10} - 2}{6} \right] $ хотя бы
одно из чисел $ k = \frac{n_{p} - 6u^{2} - 4u + 1}{2(6u - 1)} $ является целым, то число $ p $ не
является простым. Если же все эти числа $ k $ не
являются целыми, то число $ p $ - простое.

Отметим, что к первым двум простым числам 2 и 3 данный алгоритм не применяется.

Краткая сводка алгоритма в табличной форме приводится ниже .

Проверяются нечетные числа $ p > 5 $, оканчивающиеся на цифры 1, 3, 7, 9
и число $ p = 5 $. Проверяются нечетные числа $ \emph{\textbf{p > 5}} $, оканчивающиеся на цифры 1, 3, 7, 9 и число $ \emph{\textbf{p = 5}} $. {\tiny \begin{tabular}{|c|c|c|c|} \hline \multicolumn{2}{|c|}{n - четное} & \multicolumn{2}{|c|}{n - нечетное} \\ \hline n = (p + 1)/6 & n = (p - 1)/6 & n = (p + 1)/6 & n = (p - 1)/6\\ \hline $k = (n - 6u^2)/2(6u - 1),$&$k = (n - 6u^2 - 2u)/2(6u + 1),$&$ k = (n - 6u^2 - 6u + 1)/2(6u - 1)$ &$k = (n - 6u^2 - 8u - 1)/2(6u + 1)$\\ $k = (n - 6u^2)/2(6u + 1)$ &$k = (n- 6u^2 + 2u)/2(6u - 1)$ & $k = (n - 6u^2 - 6u - 1)/2(6u + 1)$ &$k = (n - 6u^2 - 4u + 1)/2(6u - 1)$\\ & или & или & или\\ & $k = (6n + 1 - b^2) / 12b =$ & $k = (6n + 15 - c^2) / 12(c - 4)$ &$k = ((3n + 5)/2 - g^2)/3(2g - 3)$\\ &$= (p - b^2)/12b$ &$1\le u \le[(\sqrt{6n + 15} - 3)/6]$ &$1\le u \le[(\sqrt{(3n + 5)/2} - 2)/3]$\\ Для целых значений & $b \le 5 \le [\sqrt{6n + 1}]$ & Для целых значений & Для целых значе-ний\\ & Для целых значений & $u = (c - 3)/6$ & $u = (g - 2)/3$\\ $ 1\le u \le[\sqrt{n/6}]$ & $u = (b - 1)/6$ & и & и\\ & и & $k = (6n + 3 - d^2)/12(d - 2)$ &$k = ((3n + 5)/2 - h^2) / 3(2h - 3)$\\ & $u = (b + 1)/6$ &$1 \le u \le [(\sqrt{6n + 3}- 3)/6]$ &\\ & & Для целых значений &$1\le u \le [(\sqrt{(3n + 5)/2} - 1)/3]$\\ & & $u = (d - 3)/6$ & Для целых значений\\ & & & $u = (h - 1)/3$\\ \hline \end{tabular} }

После всего вышеизложенного можно записать \emph{\textbf{формулу простых чисел}} в терминах и обозначениях теории множеств.

$ S = N / \{1\} / \{2n\} U \{2\} / \{6n + 3\} / \{6\{N_o\} - 1\} / \{6\{N_o\} + 1\} / \{6\{N_\rho\} - 1\} / \{6\{N_\lambda\} + 1\} $, где $ n = 1, 2, 3, \ldots $,

$ S $ - множество всех простых чисел,
$ N $ - множество натуральных чисел,
$ \{1\} $ - множество из одного числа 1,
$\{2n\} $ - множество четных чисел,
$\{2\} $ - множество из одного числа 2,
$\{6n + 3\} $ - множество нечетных чисел делящихся на 3, начиная с 9,
$\{N_o\} $ - множество пустых узлов,
$ \{6\{N_o\} - 1\} $ и $ \{6\{N_o\} + 1\} $ - множества
составных чисел пустых узлов,
$\{N_\rho\} $ - множество правосторонних узлов,
$\{6\{N_\rho\} - 1\} $ - множество составных чисел правосторонних узлов,
$ \{N_\lambda\} $ - множество левосторонних узлов,
$ \{6\{N_\lambda\} + 1\} $ - множество составных чисел левосторонних
узлов.
Формула простых чисел близнецов
$S_2 = S / \{2\} / \{6\{N_\rho\} + 1\} / \{6\{N_\lambda\} - 1\} $, где
$ S_2 $ - множество простых чисел близнецов,
$ S $ - множество всех простых чисел,
$ \{N_\rho\} $ - множество правосторонних узлов,
$ \{6\{N_\rho\} + 1\} $ - множество простых чисел правосторонних узлов,
$\{N_\lambda\} $ - множество левосторонних узлов,
$\{6\{N_\lambda\} - 1\} $ - множество простых чисел левосторонних узлов.

Л И Т Е Р А Т У Р А

1. Серпинский В. Что мы знаем и чего не знаем о простых числах. М., ГИФМЛ, 1963.
2. Наумова Л.Н. Дзета-функция Эйлера-Римана, диофантовы уравнения, простые числа и
единство математики. ISBN 5-8057-0435-8, 2004.
3. Курош А.Г. Курс высшей алгебры. М.: Наука, изд. 9-е, 1968.
4. Прасолов В.В. Многочлены. М. МЦНМО, 2001.
5. Гаусс К.Ф. Труды по теории чисел. Под общ. ред. акад. И.М. Виноградова, Изд-во АН
СССР, М., 1959.

[maxal]

Сложность этого алгоритма $\Theta(\sqrt{p})$, то есть экспоненциальна от $\log p$ (длины $p$), в то время как доказано, что эта задача имеет полиномиальное решение. Практическая ценность вашего алгоритма - нулевая.

[Леонид Вайсруб]

Это сообщение является непосредственным продолжением сообщения "Алгоритм определения простых чисел". Ограничение длины сообщения в 20 000 символов не позволяет показать примеры применения вышеизложенного алгоритм-теста в одном сообщении вместе с теоретическим материалом. Нумерация формул в этом сообщении
является продолжением нумерации сообщения "Алгоритм определения
простых чисел".
Краткое изложение алгоритма в табличной форме приводится ниже .

Проверяются нечетные числа $ \emph{\textbf{p > 5}} $, оканчивающиеся на цифры 1, 3, 7, 9 и число $ \emph{\textbf{p = 5}} $.

{\tiny \begin{tabular}{|c|c|c|c|} \hline \multicolumn{2}{|c|}{n - четное} & \multicolumn{2}{|c|}{n - нечетное} \\ \hline n = (p + 1)/6 & n = (p - 1)/6 & n = (p + 1)/6 & n = (p - 1)/6\\ \hline $k = (n - 6u^2)/2(6u - 1),$&$k = (n - 6u^2 - 2u)/2(6u + 1),$&$ k = (n - 6u^2 - 6u + 1)/2(6u - 1)$ &$k = (n - 6u^2 - 8u - 1)/2(6u + 1)$\\ $k = (n - 6u^2)/2(6u + 1)$ &$k = (n- 6u^2 + 2u)/2(6u - 1)$ & $k = (n - 6u^2 - 6u - 1)/2(6u + 1)$ &$k = (n - 6u^2 - 4u + 1)/2(6u - 1)$\\ & или & или & или\\ & $k = (6n + 1 - b^2) / 12b =$ & $k = (6n + 15 - c^2) / 12(c - 4)$ &$k = ((3n + 5)/2 - g^2)/3(2g - 3)$\\ &$= (p - b^2)/12b$ &$1\le u \le[(\sqrt{6n + 15} - 3)/6]$ &$1\le u \le[(\sqrt{(3n + 5)/2} - 2)/3]$\\ Для целых значений & $b \le 5 \le [\sqrt{6n + 1}]$ & Для целых значений & Для целых значе-ний\\ & Для целых значений & $u = (c - 3)/6$ & $u = (g - 2)/3$\\ $ 1\le u \le[\sqrt{n/6}]$ & $u = (b - 1)/6$ & и & и\\ & и & $k = (6n + 3 - d^2)/12(d - 2)$ &$k = ((3n + 5)/2 - h^2) / 3(2h - 3)$\\ & $u = (b + 1)/6$ &$1 \le u \le [(\sqrt{6n + 3}- 3)/6]$ &\\ & & Для целых значений &$1\le u \le [(\sqrt{(3n + 5)/2} - 1)/3]$\\ & & $u = (d - 3)/6$ & Для целых значений\\ & & & $u = (h - 1)/3$\\ \hline \end{tabular} }



Далее приводятся примеры применения алгоритм-теста.

Пример 1. Является ли число 2003 - простым ?

Рассмотрим рядом стоящее с ним справа четное число 2004.
Оно делится на 6, так как оно четное и делится на 3
(сумма составляющих его цифр равная 6 делится на 3). Значит
число 2004 - узел и $ n = 334 $, а число 2003
есть число вида $ 6n - 1 $. Остается проверить
удовлетворяет ли $ n = 334 $ хотя бы одному из
двух диофантовых уравнений $ n = 6uv + u - v $ или
$ n = 6uv - u + v $, где

$ u = 1,2,3,\ldots, v = 1,2,3,\ldots $ и $ v \ge u $.

$ 334 = 6uv + u - v ~~~ $ (19)

$ 334 = 6uv - u + v ~~~ $ (20)

Поскольку узел $ n = 334 $ число четное, то
$ u $ и $ v $ в (19) и в (20)
могут быть только четными или нечетными одновременно. В первую
очередь рассмотрим самый простой случай, когда $ u = v $ и тогда (19) и (20) дают $ 334 = 6u^2; 167 = 3u^2; u^2 = 167/3 $. Очевидно, что $ u $ не
целое.

Далее рассмотрим общий случай, когда $ v > u $ и
значит $ v = u + 2k $, где $ k = 1, 2, 3,\ldots $. Так как $ 1 \le u \le \sqrt{n/6} $, то $ 1 \le u \le [\sqrt{334/6}] = 7 $.
$ k = (n - 6u^2)/2(6u - 1) $ \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline u & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline $k =\frac{334 - 6u^2}{12u - 2}$ & 328/10 & 310/22 & 280/34 & 238/46 & 184/58 & 118/70 & 40/82 < 1\\ \hline \end{tabular}\\ \\ $k = (n - 6u^2)/2(6u + 1),$\\ \\ \begin{tabular}{|c|c|c|c|c|c|c|c|} \hline u & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline $k =\frac{334 - 6u^2}{12u + 2}$ & 328/14 & 310/26 & 280/38 & 238/50 & 184/62 & 118/74 & 40/86 < 1\\ \hline \end{tabular} Все значения $ k $ - не целые. Подобрать
пары целых $ u > 0 $ и $ v > 0 $,
удовлетворяющие (9) или (10) не представляется возможным, и,
следовательно, число 2003 - простое, узел $ n = 334 $ левосторонний.

Пример 2. Является ли число 4217 - простым ?

Рассмотрим рядом стоящее с ним справа четное число 4218.
Оно делится на 6, так как оно четное и делится на 3
(сумма составляющих его цифр равная 15 делится на 3). Значит
число 4218 - узел и $ n = 703 $, а число 4217
есть число вида $ 6n - 1 $. Остается проверить
удовлетворяет ли $ n = 703 $ хотя бы одному из
двух диофантовых уравнений $ n = 6uv + u - v $
или $ n = 6uv - u + v $, где $ u = 1, 2, 3, \ldots, v = 1, 2, 3, \ldots $ и $ v > u $.

$ 703 = 6uv + u - v ~~~ $ (21)

$ 703 = 6uv - u + v ~~~ $ (22)

Поскольку узел $ n = 703 $ число нечетное, то
$ u $ и $ v $ в (21) и в (22)
могут быть только разных четностей одновременно. Так как для (21)
$ 1 \le u \le [(\sqrt{6n + 15} - 3)/6],$ то $1 \le u \le [(\sqrt{4233} - 3)/6] = 10 $, где $ u = (c - 3)/6 $ и $k = (4233 - c^2) / 12(c - 4), c > 4 $
{\tiny \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline $c = 6u + 3$ & 9 & 15 & 21 & 27 & 33 & 39 & 45 & 51 & 57 & 63\\ \hline $k =\frac{4233 - c^2}{12c - 48}$ & 4152/60 & 4008/132 & 3792/204 & 3504/276 & 3144/348 & 2712/420 & 2208/492 & 1632/564 & 984/636 & 264/708 < 1\\ \hline \end{tabular} } Для (22) $ 1\le u \le [(\sqrt{4221} - 3)/6] = 10 $, где $ u = (d - 3)/6 $ и $ k =(4221 -d^2)/12(d - 2), d > 2 \\$ {\tiny \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline $d = 6u + 3$ & 9 & 15 & 21 & 27 & 33 & 39 & 45 & 51 & 57 & 63\\ \hline $k =\frac{4221 - d^2}{12d - 24}$ & 4140/84 & 3996/156 & 3780/228 & 3492/300 & 3132/372 & 2700/444 & 2196/516 & 1620/588 & 972/660 & 252/732 < 1\\ \hline \end{tabular}\\ } Все значения $ k $[math] - не целые. Подобрать пары целых [math] $ u > 0 $ и $ v > 0 $,удовлетворяющие (21) или (22) не представляется возможным,
и, следовательно, число 4217 - простое, узел $ n = 703 $ левосторонний.

Само собой хочется узнать каким является число 4219.

Слева от него четное число 4218 - узел и $ n = 703 $, а число 4219 есть число вида $ 6n + 1$.
Остается проверить удовлетворяет ли $ n = 703 $
хотя бы одному из двух диофантовых уравнений $ n = 6uv + u + v $ или $n = 6uv - u - v $, где
$ u = 1, 2, 3, \ldots, v = 1, 2, 3,\ldots, v > u $.

$ 703 = 6uv + u + v ~~~ $ (23)

$ 703 = 6uv - u - v ~~~ $ (24)

Поскольку узел $ n = 703 $ число нечетное, то
$ u $ и $ v $ в (23) и в (24) могут
быть только разных четностей одновременно. Так как для (23)
$ 1 \le u \le [(\sqrt{(3n + 5)/2} - 2)/3] $,то
$ 1 \le u \le [(\sqrt{1057} - 2)/3] = 10 $, где
$ u = (g - 2)/3 $ и $ k = (1057 - g^2)/3(2g - 3), g > 2 \\$ {\tiny \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline $g = 3u + 2$ & 5 & 8 & 11 & 14 & 17 & 20 & 23 & 26 & 29 & 32\\ \hline $k =\frac{1057 - g^2}{3(2g - 3)}$ & 1032/21 & 993/39 & 936/57 & 861/75 & 768/93 & 657/111 & 528/129 & 381/147 & 216/65 & 33/183 < 1\\ \hline \end{tabular} } Для (24) $1 \le u \le [(\sqrt{(3n + 5)/2} - 1)/3] = [(\sqrt{1057} - 1)/3] = 10 $ и $ k = (1057 - h^2)/3(2h - 3), h > 1\\$ {\tiny \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline $h = 3u + 1$ & 4 & 7 & 10 & 13 & 16 & 19 & 22 & 25 & 28 & 31\\ \hline $k =\frac{1057 - h^2}{3(2h - 3)}$ & 1041/15 & 1008/33 & 957/51 & 888/69 & 801/87 & 696/105 & 573/123 & 432/141 & 273/159 & 96/177 < 1\\ \hline \end{tabular} } Все значения $ k $ - не целые.

Подобрать пары целых $ u > 0 $ и $ v > 0 $, удовлетворяющие (23) или (24) не представляется
возможным, и, следовательно, число 4219 - простое, узел $ n = 703 $ - правосторонний.

Так как узел $ n = 703 $ является левосторонним и правосторонним, то этот узел
полный, а числа 4217 и 4219 есть числа близнецы.

Пример 3. Является ли число из семи единиц 1111111 - простым ?

Рассмотрим рядом стоящее слева от него четное число
1111110. Оно делится на 6, так как оно четное и делится на
3 (сумма составляющих его цифр равная 6 делится на 3).
Значит число 1111110 - узел и $ n = 185185 $, а
число 1111111 есть число вида $ 6n + 1 $.Остается
проверить удовлетворяет ли $ n = 185185 $ хотя
бы одному из двух диофантовых уравнений $ n = 6uv + u + v $ или $ n = 6uv - u - v $, где $ u = 1, 2, 3, \ldots, v = 1, 2, 3, \ldots $ и $ v > u $.

$ 185185 = 6uv + u + v ~~~ $ (25)

$ 185185 = 6uv - u - v ~~~ $ (26)

Поскольку узел $ n = 185185 $ число нечетное,
то $ u $ и $ v $ в (25) и в
(26) могут быть только разных четностей одновременно. Так как для
(25) $ 1 \le u \le [(\sqrt{(3n + 5)/2} - 2)/3] $,
то 1 \le u \le [(\sqrt{277780} - 2)/3] = 175 $,
где $ u = (g - 2)/3 $ и $ k = (277780 - g^2)/3(2g - 3), g > 2 $.

Для (26) $ 1 \le u \le [(\sqrt{(3n + 5)/2} - 1)/3] = [(\sqrt{277780} - 1)/3] = 175 $ и

$ k = (277780 - h^2)/3(2h - 3), h > 1 $.

Значения $ k = k(g) = (277780 - g^2)/3(2g - 3), g = 3u + 2, g > 2 $ и $ k = k(h) = (277780 - h^2)/3(2h - 3), h = 3u + 1, h > 1 $ вычисляются по несложной Excel -
программе. Все 175 значений $ k = k(g) $ и 175
значений $ k = k(h) $ не целые, значит подобрать
пары целых $ u > 0 $ и $ v > 0 $, удовлетворяющие (25) или (26) не
представляется возможным, и, следовательно, число 1111111 -
простое, узел $ n = 185185 $ - правосторонний.

Пример 4. Является ли число 4429 - простым ?

Рассмотрим рядом стоящее слева от него четное число 4428.
Оно делится на 6, так как оно четное и делится на 3
(сумма составляющих его цифр равная 18 делится на 3).
Значит число 4428 - узел и $ n = 738 $, а число
4429 есть число вида $ 6n + 1 $. Остается
проверить удовлетворяет ли $ n = 738 $ хотя бы
одному из двух диофантовых уравнений $ n = 6uv + u + v $ или $ n = 6uv - u - v $, где $ u = 1, 2, 3, \ldots, v = 1, 2, 3, \ldots, v > u $.

$ 738 = 6uv + u + v ~~~$ (27)

$ 738 = 6uv - u - v ~~~$ (28)

Поскольку узел $ n = 738 $ число четное, то
$ u $ и $ v $ в (27) и в (28)
могут быть только четными или нечетными одновременно.

$ k = (6n + 1 - b^2) /12b = (p - b^1)/12b$. Следует
проверить принимает ли $ k $ целые значения для
целых $ 5 \le b \le [\sqrt{6n + 1}] = [\sqrt{4429}] = 66 $, получаемых по следующим правилам $ b = 6u + 1 $ и $ b = 6u - 1 $, в которых $ 1 \le u \le 10 \\$ {\tiny \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline u & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline $b = 6u + 1$ & 7 & 13 & 19 & 25 & 31 & 37 & 43 & 49 & 55 & 61\\ \hline $k =\frac{4429 - b^2}{12b}$ & $\frac{4380}{84}$ & $\frac{4260}{156}$ & $\frac{4068}{228}$ & $\frac{3804}{300}$ & $\frac{3468}{372}$ & $\frac{3060}{444}$ & $\frac{2580}{516} = 5$ & $\frac{2028}{588}$ & $\frac{1404}{660}$ & $\frac{708}{732} < 1$\\ \hline \end{tabular} } {\tiny \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline u & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline $b = 6u - 1$ & 5 & 11 & 17 & 23 & 29 & 35 & 41 & 47 & 53 & 59 & 65\\ \hline $k =\frac{4429 - b^2}{12b}$ & $\frac{4404}{60}$ & $\frac{4308}{132}$ & $\frac{4140}{204}$ & $\frac{3900}{276}$ & $\frac{3588}{348}$ & $\frac{3204}{420}$ & $\frac{2748}{492}$ & $\frac{2220}{564}$ & $\frac{1620}{636}$ & $\frac{948}{708}$ & $\frac{204}{780} < 1$\\ \hline \end{tabular} }

Среди 21- го допустимого значения $ k $ все кроме
одного - не целые. При $ u = 7, b = 43, k = 5, v = 17 $ получается $ n = 738 = 6*7*17 + 7 +17 = 738 $. Следовательно число $ p = 4429 =(6u + 1)(6v + 1) = 43*103 $ - составное. Так как $ b = 6u + 1$, значит $ b $ есть делитель исходного
числа, т.е. $ b = 43 $.

В сообщении "Алгоритм определения простых чисел" приводится
\emph{\textbf{формула простых чисел}} в терминах и
обозначениях теории множеств.

$ S = N / \{1\} / \{2n\} U \{2\} / \{6n + 3\} / \{6\{N_o\} - 1\} / \{6\{N_o\} + 1\} / \{6\{N_\rho\} - 1\} / \{6\{N_\lambda\} + 1\} $, где $ n = 1, 2, 3, \ldots $,

$ S $ - множество всех простых чисел,

$ N $ - множество натуральных чисел,

$ \{1\} $ - множество из одного числа 1,

$\{2n\} $ - множество четных чисел,

$\{2\} $ - множество из одного числа 2,

$\{6n + 3\} $ - множество нечетных чисел делящихся
на 3, начиная с 9,

$\{N_o\} $ - множество пустых узлов,

$ \{6\{N_o\} - 1\} $ и $ \{6\{N_o\} + 1\} $ - множества составных чисел пустых узлов,

$\{N_\rho\} $ - множество правосторонних узлов,

$\{6\{N_\rho\} - 1\} $ - множество составных чисел
правосторонних узлов,

$ \{N_\lambda\} $ - множество левосторонних узлов,

$ \{6\{N_\lambda\} + 1\} $ - множество составных
чисел левосторонних узлов.

Формула простых чисел близнецов

$S_2 = S / \{2\} / \{6\{N_\rho\} + 1\} / \{6\{N_\lambda\} - 1\} $, где

$ S_2 $ - множество простых чисел близнецов,

$ S $ - множество всех простых чисел,

$ \{N_\rho\} $ - множество правосторонних узлов,

$ \{6\{N_\rho\} + 1\} $ - множество простых чисел
правосторонних узлов,

$\{N_\lambda\} $ - множество левосторонних узлов,

$\{6\{N_\lambda\} - 1\} $ - множество простых чисел
левосторонних узлов.

\emph{\textbf{ Замечание }} относительно гипотезы Гольдбаха.

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

$$ S / \{2\} + S / \{2\} = \{2n\} / \{2, 4\} , $$

где $ S $ - множество всех простых чисел, $\{2n\} $ - множество четных чисел, $ n = 1, 2, 3, \ldots , \{2, 4\} $ - множество из двух чисел 2 и 4.

[venco]

Ваш алгоритм имеет сложность $\sqrt n\over3$ делений, поэтому может конкурировать только с одним из самых простых методов определения простоты - деление на все числа до $\sqrt n$. Этот метод используют только из за его простоты, когда лень писать что-то более сложное.
Поэтому, чтобы составить конкуренцию, Ваш метод должен быть проще в реализации.
Сравните, например, простой алгоритм с $\sqrt n$ делений:

Используется синтаксис C++

bool is_prime(int n)
{
    for ( int i = 2; i*i <= n; ++i )
        if ( n%i == 0 ) return false;
    return true;
}
 

И чуть оптимизированный алгоритм с $\sqrt n \over 3$ делений, как и у Вашего алгоритма:

Используется синтаксис C++

bool is_prime(int n)
{
    if ( n > 2 && n%2 == 0 ) return false;
    if ( n > 3 && n%3 == 0 ) return false;
    for ( int i = 5; i*i <= n; i += 6 ) {
        if ( n%i == 0 ) return false;
        if ( n%(i+2) == 0 ) return false;
    }
    return true;
}
 

Можно ли Ваш алгоритм записать так же компактно?

[age]

Леонид Вайсруб в сообщении #335009 писал(а):

Значения $ k = k(g) = (277780 - g^2)/3(2g - 3), g = 3u + 2, g > 2 $ и $ k = k(h) = (277780 - h^2)/3(2h - 3), h = 3u + 1, h > 1 $ вычисляются по несложной Excel -
программе.

Хорошо, а если будет число состоящее из 307 единиц, то в какой программе придется вычислять?