2014 dxdy logo

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

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




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу Пред.  1 ... 42, 43, 44, 45, 46  След.
 
 Re: Поиск простых чисел
Сообщение15.02.2014, 12:21 
Заблокирован


27/09/10

248
Россия г.Тюмент
Прошу прощение хотел добавить правки что то нет. У меня к вам такой вопрос существует ли алгоритмы для всех бес исключения чисел.В смысле конечно не так как скажем для чисел Ферма и т п а дающие хоть какое то упрощение.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.02.2014, 10:30 


26/02/14
18
Скажите, если взять известный многочлен от 26 переменных, множество положительных значений которого совпадает с множеством всех простых чисел, то что можно сказать о множестве тех значений переменных (неотрицательных целочисленных), на которых достигается конкретное простое число? Оно хотя бы конечно? Я просмотрел статью пока только поверхностно и не могу ответить сам.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение01.03.2014, 12:04 


03/10/06
826
Тестом для простых чисел Мерсенна является тест Люка-Лемера. Но на самом ли деле он самый простой. Вроде бы проходит такой же тест, как и для чисел Ферма.
$3^{\frac{M_n-1}{2}}+1={0} \mod { M_n}$
Код:
m := 3;
for n:= 3 to 1280 do
if not rab_primetest(n) then
  continue;
end;
p := 2**n-1;
s := m;
for i:=2 to n do
  s:=(s*s)mod p;
end;
if (0=(s+m) mod p)then
  writeln(n);
end;
end.
3
5
7
13
17
19
31
61
89
107
127
521
607
1279
Код для Aribas.

$3^{\frac{M_n-1}{2}}+1={0} \mod { M_n}$
Пояснение к этой формуле. В тесте Люка-Лемера используется последовательность Люка с $P=4,Q=1$.
Они дают для квадрата дискриминанта $D^2=P^2-4Q$ число $12$.
Для определения значений нужных чисел в последовательности Люка будет использоваться значение числа $(D^{M_n-1} \mod M_n)$ или $(12^{\frac{M_n-1}{2}} \mod M_n)$,
но $(12^{\frac{M_n-1}{2}}+1)=0 \mod M_n$
из чего следует, что и $(3^{\frac{M_n-1}{2}}+1)=0 \mod M_n$

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение13.06.2014, 13:27 
Аватара пользователя


07/07/09
346
Минск
serega57 в сообщении #826761 писал(а):
Прошу прощение хотел добавить правки что то нет. У меня к вам такой вопрос существует ли алгоритмы для всех бес исключения чисел.В смысле конечно не так как скажем для чисел Ферма и т п а дающие хоть какое то упрощение.

Есть ещё алгоритм "АССА" http://klm.z2.by/ который здесь обсуждался. В заданном интервале находит все простые числа.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение19.11.2016, 21:48 


20/03/14
12041
 !  Izigro
Пост с саморекламой, идентичный перенесенному в Карантин, удален. Предупреждение за саморекламу и действий в обход указаний модератора.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение20.11.2016, 16:31 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Тема захватила внимание, прочитал первые 5 страниц, но было неохота читать все 45. Подскажите, SerjeyMinsk выложил свой гениальный алгоритм?

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение22.07.2017, 02:20 


19/07/17

20
 !  Modest: Самореклама удалена.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение02.08.2017, 03:59 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
CherkasovMY, если хотите обсуждать — создайте свою тему и изложите в ней суть дела.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение27.11.2017, 23:57 
Аватара пользователя


07/07/09
346
Минск
dimkadimon в сообщении #1170337 писал(а):
Тема захватила внимание, прочитал первые 5 страниц, но было неохота читать все 45. Подскажите, SerjeyMinsk выложил свой гениальный алгоритм?

Да, вот он http://klm.z2.by/

-- Пн ноя 27, 2017 23:58:47 --

Someone в сообщении #1237583 писал(а):
CherkasovMY, если хотите обсуждать — создайте свою тему и изложите в ней суть дела.

Благодарю!

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.11.2017, 04:45 


21/05/16
4292
Аделаида
Мне одному кажется что алгоритм длится очень долго? Он даже для числа 5555 считал несколько секунд.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.11.2017, 05:21 
Заслуженный участник


20/08/14
11065
Россия, Москва
Дык вам же прямо сказали
Цитата:
с экспоненциональной сложностью
Ну и чего же тогда вообще хотите? Да и ещё на чём написан неизвестно (может там вообще интерпретируемый язык :facepalm:). Для числа $9997$ он вообще превысил отведённое ему время в $30$с и вылетел.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.11.2017, 08:32 
Заслуженный участник


20/08/14
11065
Россия, Москва
dimkadimon, kotenok gav
Почитал тему, забавно.
Но практической ценности ни в одном из представленных алгоритмов (а их тут было несколько) не обнаружено. Все тормозные, некоторые лишь слегка, большинство страшно.
Конкретно про ASSA, как только был показан код, то сразу нашли оценку сложности, она оказалась в $\sim \ln n$ раз больше решета Эратосфена, на практике (после оптимизации!) время вдвое хуже. В явном виде оценки сложности есть на 13-й странице.
Причина же тормозов на сайте скорее всего в недостатках используемого языка программирования (ну очень похоже на интерпретатор).
Для сравнения, primesieve (одна из самых быстрых программ) просеивает все числа до $10^9$ менее секунды (на одно ядро и 1ГГц, т.е. грубо порядка 1 такта на число).

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.11.2017, 09:17 
Аватара пользователя


07/07/09
346
Минск
Dmitriy40 в сообщении #1269795 писал(а):
dimkadimon, kotenok gav
Почитал тему, забавно.
Но практической ценности ни в одном из представленных алгоритмов (а их тут было несколько) не обнаружено. Все тормозные, некоторые лишь слегка, большинство страшно.
Конкретно про ASSA, как только был показан код, то сразу нашли оценку сложности, она оказалась в $\sim \ln n$ раз больше решета Эратосфена, на практике (после оптимизации!) время вдвое хуже. В явном виде оценки сложности есть на 13-й странице.
Причина же тормозов на сайте скорее всего в недостатках используемого языка программирования (ну очень похоже на интерпретатор).
Для сравнения, primesieve (одна из самых быстрых программ) просеивает все числа до $10^9$ менее секунды (на одно ядро и 1ГГц, т.е. грубо порядка 1 такта на число).

Во-первых тут математика жешь, а не вычислительная техника. Алгоритм "АССА" - детерминированный и это в другой плоскости "тормозов".
Второе: А вы прочитали или проверили сложность, что так заявляете? Проверьте сложность алгоритма решета Эратосфена в заданном квадрате больших чисел и сравните сложность с АССА, пожалуйста. Возьмите, любое большее $10^9, к примеру.
Язык программирования там PHP и это демонстрационная версия. Там таймаут еще к тому же и ограничение на 4 знака. Это да. Он висит уже лет 7 там.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.11.2017, 12:26 
Заслуженный участник


20/08/14
11065
Россия, Москва
По математике претензий нет. А вот полезность на практике под вопросом (не смог придумать ситуации в которой этот алгоритм выигрывал бы у решета).

SerjeyMinsk в сообщении #1269801 писал(а):
Второе: А вы прочитали или проверили сложность, что так заявляете?
Я не заявлял, я лишь пересказал своими словами уже проведённый анализ и измерения. Причём сразу же дал ссылки на источники.

SerjeyMinsk в сообщении #1269801 писал(а):
Проверьте сложность алгоритма решета Эратосфена в заданном квадрате больших чисел и сравните сложность с АССА, пожалуйста.
Нет смысла, за меня для Вашего алгоритма это проделали 8 лет назад, а для решета Эратосфена ещё сильно раньше.
Хотя ... Не анализ, а тест, пожалуйста. Сравнил время счёта трёх программ для одного и того числа (которое подавалось на вход Вашей программы и квадрат которого вместе с квадратом предыдущего нечётного подавались на вход primesieve и моей программы), primesieve, одна из моих реализаций решета Эратосфена, Вашей, venco (оптимизированная ваша):
Используется синтаксис Text
                primesieve      моё решето     SerjeyMinsk     venco
10^4+3          0.000            0.095            0.074           0.001
10^5+3          0.001            0.095            7.365           0.011
10^6+3          0.005            0.105          719.883           0.294
10^7+3          0.037            0.215            ?               3.467
10^8+3          0.409            2.318            ?              43.841
10^9+3          7.259           22.154            ?             571.218
Время в секундах. Знак вопроса - завершения не дождался.
Про сложность $O(n^2)$ для Вашей программы было указано здесь и следующим сообщением. Вероятно это огрехи программиста.

 Профиль  
                  
 
 Re: Поиск простых чисел
Сообщение28.11.2017, 13:07 
Аватара пользователя


07/07/09
346
Минск
Dmitriy40, есть алгоритм АССА и есть программа по этому алгоритму. Алгоритм находит все простые числа между заданными квадратами, а как, простите, их найдет решето Эратосфена, пока не перелопатит весь ряд до них? Программа не оптимизирована, нет исключения из памяти массива чисел и вобще это наипростейшая реализация о которой никто больше и не заботился. У нас есть и полиномиальный алгоритм уже давно и новая быстрая квантостойкая хэш-функция, которая пригодна для тех практических целей о которых вы говорите, а толку то.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 682 ]  На страницу Пред.  1 ... 42, 43, 44, 45, 46  След.

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



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

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


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

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