Простые числа вида p1+p2+p1p2

[Ioda]

Рассмотрим два простых числа $p_1$ и $p_2$ ($p_1>p_2$).
Тогда число равное $p_1+p_2+p_1p_2=q$ является простым тогда и только тогда, когда все остатки от деления $q$ на все простые числа $p_i$ ,такие что $p_i <\frac{p_1+1}{2}$,ненулевые . Вопрос :легче ли данный алгоритм проверки простоты сгенерированного числа хотя бы одного из существующих алгоритмов проверки простоты числа?

[mihaild]

$p_1 = 17$, $p_2 = 7$, $p_1 + p_2 + p_1 p_2 = 143 = 11 \cdot 13$, $11 > \frac{17 + 1}{2}$.

[Ioda]

mihaild, согласен. Надо исправить : $\frac{q-1}{2}>p_i$
Хотя помню вводил ограничения менее жесткие и более обоснованные.

[Dmitriy40]

Ioda в сообщении #1329603 писал(а):

Надо исправить :$\frac{q-1}{2}>p_i$

Я правильно понял, Вы предлагаете делить на все простые до половины проверяемого числа? Но ведь достаточно лишь до $\sqrt{q}$, что значительно меньше.
Так что нет, предлагаемое абсолютно не легче, а намного-намного труднее. И от формы $p_1+p_2+p_1p_2$ уже никак не зависит.

[Ioda]

Dmitriy40 ,не легче даже если брать рассматриваемое вами условие?

[Dmitriy40]

Ioda
Нет, это банальный метод проверки всех делителей, для больших чисел он ОЧЕНЬ-ОЧЕНЬ долгий. Нереально долгий.

[Ioda]

Dmitriy40, то есть решение системы сравнений слишком долгое, верно?

[Dmitriy40]

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

[Ioda]

Dmitriy40, а если поставить задачу примерно наоборот : пусть простое число $q$ представимо в виде $q=p_1+p_2+p_1p_2$ ,где $p_1$ простое . Тогда является ли простым $p_2$ ? (Очевидно что $p_2$ может быть составным у которого в простых делителях нет $p_1$). Или более обобщенно и интересно :
Всякое ли простое число представимо в виде $q=p_1+p_2+p_1p_2$ ,где $p_1$ простое, а $p_2$ составное? Или: Бесконечно ли множество простых чисел вида $q=p_1+p_2+p_1p_2$ ,где $p_1$ и $p_2$ простые?

[Someone]

Вообще-то, ввиду равенства $q+1=(p_1+1)(p_2+1)$, представления числа $q$ в виде $q=p_1+p_2+p_1p_2$ определённым образом связаны с разложением числа $q+1$ на два множителя.