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

[Droog_Andrey]

Однако это не доказательство простоты.

Вдруг это самое ваше число как раз и просочилось?

Пользуйтесь ECPP или APRT-CL.

[VAL]

Droog_Andrey в сообщении #280448 писал(а):

Однако это не доказательство простоты.

Вы не поверите, но в курсе!

Цитата:

Вдруг это самое ваше число как раз и просочилось?

Готов заключить пари

Цитата:

Пользуйтесь ECPP или APRT-CL.

А это что за "звери"?

[Droog_Andrey]

Это не подход математика.

ECPP и APRT-CL - методы доказательства простоты чисел. Погуглите.

[VAL]

Droog_Andrey в сообщении #280650 писал(а):

Это не подход математика.

От химика слышу!

Цитата:

ECPP и APRT-CL - методы доказательства простоты чисел. Погуглите.

Пришлось. Надежда на дармовщиму не оправдалась
Первая я же ссылка вывела меня на Ваше письмо (dxdy в фаворе!)
Затем я узнал, что ECPP - Европейская Конфедерация психоаналитической психотерапии...

Ну а теперь вопрос без смайликов.
Утверждается, что ECPP имеет временную сложность $O((\log n)^{5+\epsilon})$. Получается, что это лучше, чем у улучшенного AKS? Там ведь шестая степень? Или просто $\epsilon$, если не повезет, может быть большим?

[Droog_Andrey]

ECPP при нормальной реализации имеет сложность около $\log^4n$.

VAL в сообщении #280698 писал(а):

Надежда на дармовщиму не оправдалась

http://primes.utm.edu/prove/prove4.html

[VAL]

Droog_Andrey в сообщении #280999 писал(а):

ECPP при нормальной реализации имеет сложность около $\log^4n$.

С ума сойти! Вроде бы только что (по крайней мере в текущем тысячелетии) полиномиальность проверки на простоту доказали и радовались 12-й степени полинома.

Цитата:

VAL в сообщении #280698 писал(а):

Надежда на дармовщиму не оправдалась

http://primes.utm.edu/prove/prove4.html

Спасибо!
Интересный ресурс, с удовольствием поковыряюсь!

[Droog_Andrey]

VAL, я написал "около". Практически это так, однако теоретически полиномиальность ECPP не доказана.

[mag_spb]

А существуют ли математические функции результатом которых былаб последовательность простых чисел. Но при этом не использующие в своем составе известные простые числа.

[Droog_Andrey]

http://primes.utm.edu/glossary/xpage/Ma ... cPoly.html

http://mathworld.wolfram.com/Prime-Gene ... omial.html

http://en.wikipedia.org/wiki/Formula_for_primes

[mag_spb]

Цитата:

http://primes.utm.edu/glossary/xpage/Ma ... cPoly.html ...

Спасибо за информацию, но это либо теоретические формулы, либо реальные формулы, работающие в
коротком диапазоне.
А есть ли функции типа F(n)=(2*n+1)*k(n) которые взависимости от n принимают значение либо 0 либо простое число, использующие только сложение, вычетание, умножение, деление работающие от 0 до 2^31

[mag_spb]

Похоже я не дождусь ответа. Очевидно всем надоела эта тема. Но вопрос не в этом. Просто мне интересно я вывел уже известную формулу или это что-то новое. То, что данная функция будет иметь вышеуказанные значения при любом n это точно.

[venco]

Подобная формула уже известна: http://en.wikipedia.org/wiki/Formula_for_primes#Recurrence_relation
Правда практического значения она не имеет, т.к. слишком редко даёт простые числа, и содержит много повторов.
Если у вас что-то более осмысленное, то выкладывайте, оценим.

-- Ср янв 20, 2010 15:38:00 --

mag_spb в сообщении #282103 писал(а):

Просто мне интересно я вывел уже известную формулу или это что-то новое.

Как мы это узнаем, если вы свою формулу не публикуете?

[mag_spb]

Так весь вопрос в том "кто первый встал...". Если это что-то новое, то потом запаришься доказывать, что ты был первым. А если это уже есть, то стоит почитать, оценить и решить что у меня получилось.

[venco]

Я почти уверен, что ваша "функция" - разновидность решета Эратосфена, или даже ещё примитивнее.

[mag_spb]

Цитата:

Подобная формула уже известна: http://en.wikipedia.org/wiki/Formula_fo ... relation...

Данная формула предполагает вычисление НОД.

Решето Эратосфена предполагает знание ранее полученных простых чисел. У меня же подставляя любое значение n функция принимает значение либо 0 либо простое число.

Прошу прощения за мою некоторую наивность или глупость, я не математик по образованию. Но неужели нет работающих формул, которые бы не использовали ранее полученные результаты. А что касается "решета", то практически все формулы на которые давались ссылки можно подвести под это понятие.