2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Формула проверки числа на простоту
Сообщение20.10.2016, 05:57 
Аватара пользователя


12/10/16
134
Almaty, Kazakhstan
Часто, когда нужно проверить число на простоту, использую 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 $ за доли секунд. Может кому пригодиться.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение20.10.2016, 06:46 
Аватара пользователя


21/09/12
1142
Soul Friend в сообщении #1161272 писал(а):
Фейлит как нечетные так и четные

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

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение20.10.2016, 06:47 
Аватара пользователя


12/10/16
134
Almaty, Kazakhstan
всё учу и не могу никак осилить ангийский

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение20.10.2016, 06:51 
Аватара пользователя


21/09/12
1142
Soul Friend
Ещё бы русский подправить. :D

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение20.10.2016, 08:23 
Аватара пользователя


12/10/16
134
Almaty, Kazakhstan
хочу уточнить, там умножаются остатки от деления. Если встечается делитель числа то получается $0$ , и все умажается на $0$ , в результате число составное.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение04.03.2017, 15:53 
Аватара пользователя


12/10/16
134
Almaty, Kazakhstan
можно и так, но не лучше:
$$\mod \left( \frac{\prod_{n=2}^{\frac{x}{3}}(n^2)}{x} \right)$$
только, здесь проверяются нечётные числа.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 13:57 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 15:15 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 15:19 


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

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 15:31 
Аватара пользователя


12/10/16
134
Almaty, Kazakhstan
Последняя формула на OEIS A283361.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 15:55 


20/08/14
2540
Россия, Москва
Неа, там нигде нет деления на $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)?!

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 15:59 
Аватара пользователя


12/10/16
134
Almaty, Kazakhstan
так это я поправил там под правила OEIS )), просто здесь на dxdy я написал формулу под программу mathlab для смартфонов.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 16:10 


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

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

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 16:26 
Аватара пользователя


12/10/16
134
Almaty, Kazakhstan
Dmitriy40 в сообщении #1198128 писал(а):
особенно если исключить проверку чётных делителей

легко :$$\prod_{n=2}^{ \frac {\sqrt{x}}{2}+1}(x \mod (2n-1)) $$
только теперь проверяются только нечётные числа.

 Профиль  
                  
 
 Re: Формула проверки числа на простоту
Сообщение08.03.2017, 17:22 


20/08/14
2540
Россия, Москва
Во, да, теперь оно всего лишь раз в 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$ составное - вылетит (надеюсь не в синий экран смерти ;-)) с ошибкой деления на ноль и не будет перебирать все делители. :mrgreen:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group