Формула проверки числа на простоту

[Soul Friend]

Часто, когда нужно проверить число на простоту, использую apk MathLab в телефоне, в ней же ввожу формулу:

$$ \prod_{n=2}^{\sqrt{x}}{(\mod(x,n))} $$

Это сокращенный вид перебора делителей:

$$ \mod (\frac x 2 \cdot \frac x 3 \cdot \ldots \cdot \frac {x}{ \sqrt{x} } ) $$

Если результат равен нулю, то $x$ составное число, а если иначе то простое. Фейлит как нечетные так и четные. Производит расчет чисел до $ 10^9 $ за доли секунд. Может кому пригодиться.

[atlakatl]

Soul Friend в сообщении #1161272 писал(а):

Фейлит как нечетные так и четные

Жаргон "фейлить" от англ. fail - потерпеть неудачу. А в этом алгоритме всё путём.

[Soul Friend]

всё учу и не могу никак осилить ангийский

[atlakatl]

Soul Friend
Ещё бы русский подправить.

[Soul Friend]

хочу уточнить, там умножаются остатки от деления. Если встечается делитель числа то получается $0$ , и все умажается на $0$ , в результате число составное.

[Soul Friend]

можно и так, но не лучше:

$$\mod \left( \frac{\prod_{n=2}^{\frac{x}{3}}(n^2)}{x} \right)$$

только, здесь проверяются нечётные числа.

[Sonic86]

У любой формулы проверки на простоту есть как минимум 2 аспекта:
1. Теоретический: насколько ее удобно было бы использовать в доказательствах.
2. Практический: насколько с ее помощью было бы удобно проверять число на простоту.
Теоретический аспект - штука сложная, но вот с практическим аспектом почти все ясно:
Если дана какая-то формула $F(p)$, которую надо вычислить для проверки числа $p$ на простоту, то чем медленнее вычисляется $F$, тем менее она интересна в практическом аспекте. Медленность формулы оценивается прежде всего ее асимптотикой. Если у $F$ большая асимптотика, то никому такая формула в практическом аспекте не будет интересна - такие формулы можно изобретать пачками, но толку от них не будет никакого в этом плане.
Самый известный пример, который изучают в школе - решето Эратосфена. Для его работы требуется грубо говоря порядка $O(\sqrt{p})$. Отсюда вывод - если формула $F$ вычисляется медленнее, чем за $O(\sqrt{p})$, то она не будет никому нужна для проверки. Зачем ее использовать, если есть решето Эратосфена, которое работает быстрее.
У Вашей формулы асимптотика, очевидно, больше, чем $O(x)$ (просто потому что надо перемножить $\frac{x}{3}-1=O(x)$ чисел). Отсюда какой вывод?

[Soul Friend]

Sonic86 , полностью согласен на счёт асимптотики, только раньше для меня не было очевидным, что теорему Вильсона можно сократить до $(floor(\frac{p}{3}))!$. На OEIS попросили доказать это, что я и сделал на сколько ума хватило)).

[Dmitriy40]

Сравнение ассимптотик конечно правильно, в теории, но на практике в конкретном вычислительном устройстве может не оказаться встроенной функции решета, а произведение ряда - оказаться. И тогда эти формулы имеют право на жизнь, даже несмотря на явную неоптимальность. Тем более они достаточно просты, по сравнению с гораздо более быстрыми вероятностными тестами на простоту. А первая имеет ровно ту же асимптотику что и решето - $O(\sqrt{x})$. Другое дело что решето выдаст не одно простое число, а сразу много, да и константа в $O()$ меньше, зато и существенно сложнее в реализации.
Ещё, диапазон всего лишь $10^9$ это совсем немного, решето выдаст все простые числа во всём диапазоне за секунду, а не лишь одно. Вот сравнить скорость где-нибудь около $10^{20}$ ...
Так что достоинство первой формулы - простота. Если ещё и все чётные делители не проверять ...
Последнюю формулу извините не понимаю, что по какому модулю считается.

[Soul Friend]

Последняя формула на OEIS A283361.

[Dmitriy40]

Неа, там нигде нет деления на $x$ или $n$, зато чётко указано по какому модулю считается и везде он $2n-1$. Так что там формула совершенно другая:

$$ \left(\prod_{n=2}^{\lfloor 2x/3 \rfloor}{n^2}\right) \mod (2x-1)$$

С Вашей она ну никак не совпадает.
Кстати, вместо $floor(x)$ в формулах тут вполне можно пользоваться $\lfloor x \rfloor$.

Upd. И кстати, разве в этом MatLab для телефона нету встроенной функции isprime(x)?!

[Soul Friend]

так это я поправил там под правила OEIS )), просто здесь на dxdy я написал формулу под программу mathlab для смартфонов.

[Dmitriy40]

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

Вот самая первая формула в теме - да, простая и полезная. И всего лишь в десяток-два раз медленнее решета (особенно если исключить проверку чётных делителей). Модуль правда тоже записан не совсем правильно, надо было $\prod_{n=2}^{\lfloor \sqrt{x} \rfloor}{(x \mod n)}$, но хотя бы понятно что на что делится для взятия остатка.

[Soul Friend]

Dmitriy40 в сообщении #1198128 писал(а):

особенно если исключить проверку чётных делителей

легко :

$$\prod_{n=2}^{ \frac {\sqrt{x}}{2}+1}(x \mod (2n-1)) $$

только теперь проверяются только нечётные числа.

[Dmitriy40]

Во, да, теперь оно всего лишь раз в 5 медленнее решета для чисел около $10^9$ и раз в 11 для чисел порядка $10^{20}$.

Предложу ещё вариант как ускорить проверку для составных чисел:

$$\frac{1}{x \bmod 2}+\sum\limits_{n=1}^{\frac{\sqrt{x}}{2}}\frac{1}{x \bmod (2n+1)}$$

Если число $x$ составное - вылетит (надеюсь не в синий экран смерти ) с ошибкой деления на ноль и не будет перебирать все делители.