2014 dxdy logo

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

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





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


12/10/16
196
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
1480
Soul Friend в сообщении #1161272 писал(а):
Фейлит как нечетные так и четные

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

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


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

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


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

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


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

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


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

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


08/04/08
8373
У любой формулы проверки на простоту есть как минимум 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
196
Almaty, Kazakhstan
Sonic86 , полностью согласен на счёт асимптотики, только раньше для меня не было очевидным, что теорему Вильсона можно сократить до $(floor(\frac{p}{3}))!$. На OEIS попросили доказать это, что я и сделал на сколько ума хватило)).

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


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

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


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

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


20/08/14
3262
Россия, Москва
Неа, там нигде нет деления на $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
196
Almaty, Kazakhstan
так это я поправил там под правила OEIS )), просто здесь на dxdy я написал формулу под программу mathlab для смартфонов.

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


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

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

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


12/10/16
196
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
3262
Россия, Москва
Во, да, теперь оно всего лишь раз в 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  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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