Поиск простых чисел

[serega57]

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

[proba]

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

[yk2ru]

Тестом для простых чисел Мерсенна является тест Люка-Лемера. Но на самом ли деле он самый простой. Вроде бы проходит такой же тест, как и для чисел Ферма.
$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$

[SerjeyMinsk]

serega57 в сообщении #826761 писал(а):

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

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

[Lia]

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

[dimkadimon]

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

[CherkasovMY]

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

[Someone]

CherkasovMY, если хотите обсуждать — создайте свою тему и изложите в ней суть дела.

[SerjeyMinsk]

dimkadimon в сообщении #1170337 писал(а):

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

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

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

Someone в сообщении #1237583 писал(а):

CherkasovMY, если хотите обсуждать — создайте свою тему и изложите в ней суть дела.

Благодарю!

[kotenok gav]

Мне одному кажется что алгоритм длится очень долго? Он даже для числа 5555 считал несколько секунд.

[Dmitriy40]

Дык вам же прямо сказали

Цитата:

с экспоненциональной сложностью

Ну и чего же тогда вообще хотите? Да и ещё на чём написан неизвестно (может там вообще интерпретируемый язык ). Для числа $9997$ он вообще превысил отведённое ему время в $30$с и вылетел.

[Dmitriy40]

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

[SerjeyMinsk]

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

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

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

[Dmitriy40]

По математике претензий нет. А вот полезность на практике под вопросом (не смог придумать ситуации в которой этот алгоритм выигрывал бы у решета).

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)$ для Вашей программы было указано здесь и следующим сообщением. Вероятно это огрехи программиста.

[SerjeyMinsk]

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