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

[Droog_Andrey]

serval, для больших $P$ так получается быстрее. Для маленьких $P$ быстрее Эратосфен. Но и аналитические методы используются иногда. Например, таким методом было найдено, что количество простых, не превышающих $10^{24}$, равно

$$18435599767349200867866$$

(правда, при расчёте была допущена справедливость гипотезы Римана, но характер сходимости к целому числу указывает на то, что расчёт будет справедлив и без этого допущения, только станет более громоздким).

[serval]

Цитата:

количество простых, не превышающих

Об оценке количества простых чисел в заданном интервале я знаю.
А есть ли способ вычислить (явно выписать число и сказать - оно заведомо простое) конкретное простое число зная даже все предшествующие ему?
Я не слышал о таком способе.

[Jnrty]

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

[serval]

Фомула-то есть, я знаю. А вот можно ли с ее помощью вычислить конкретное простое число?
Взять эту формулу, посчитать - и выписать простое число?
Не доказать, что с ее помощью можно вычислить - а взять и вычислить?

[Jnrty]

Так возьмите и вычислите. Кто мешает-то?

[serval]

А были такие, которые ее (эту формулу) "взяли и вычислили"? Если нет - кто мешает?

[arseniiv]

SerjeyMinsk в сообщении #393099 писал(а):

А что такое средняя снежинка?

Вероятность того, что в одном месте или в одно время выпадут две идентичные снежинки, почти нулевая. Но толку от уникальности снежинок нет, кроме каких-нибудь особенно красивых (а это субъективно) или кому-то полезных.
То есть ровно это:

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

Обычный школьник может придумать множество уникальных алгоритмов поиска простых чисел. Но практический интерес они вряд ли будут представлять.

[Droog_Andrey]

serval в сообщении #393286 писал(а):

А есть ли способ вычислить (явно выписать число и сказать - оно заведомо простое) конкретное простое число зная даже все предшествующие ему?

Вычисляете спектр флуктуаций $\pi$-функции и по нему экстраполируете её за пределы данного простого числа. Чем оно больше, тем больше "ступенек", которым соответствуют последующие простые числа, найдёте в области экстраполяции.

[SerjeyMinsk]

Droog_Andrey
Вы хоть разницу понимаете в детерминированном методе и вероятностном?
А также в разнице проблем математики и вычислительной технике?
Если уж школьник может придумать множество алгоритмов по поиску простых чисел, то я так понимаю вам это вообще как орешки щелкать. Не выдадите ли тут на всеобщее рассмотрение хоть один детерминированный в вашем исполнении? Без теории вероятностей.

[Droog_Andrey]

SerjeyMinsk, причём здесь вероятности? Вероятностные методы - это, скажем, тест BPSW.

[serval]

Цитата:

Вычисляете спектр флуктуаций -функции и по нему экстраполируете её за пределы данного простого числа. Чем оно больше, тем больше "ступенек", которым соответствуют последующие простые числа, найдёте в области экстраполяции.

Этим способом можно получить конкретное заведомо простое число?
Чтобы потом не тратиться на проверку его простоты?

[iig]

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

Заблуждаетесь! Простые числа указанного Вами размера современные программы за одну секунду способны генерить миллионами. Иное дело разложение на множители. Но эти задачи (проверка на простоту и факторизация) даже близко рядом не лежали.

Я бы предложил такой алгоритм, который последовательно находит все множители, возможно, так будет быстрее, чем находить только простые.
Кроме того на множестве комплексных целых число 5, например, не простое. Так появляется задача найти только такие числа или все простые, но без них.

[Someone]

iig в сообщении #393702 писал(а):

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

Свежайшая мысль. За все годы существования вычислительной техники никто не додумался.

serval в сообщении #393356 писал(а):

А были такие, которые ее (эту формулу) "взяли и вычислили"?

"Вычислили формулу"??? Вам предлагалось не "вычислять формулу", а воспользоваться готовой формулой для вычисления простого числа.

serval в сообщении #393356 писал(а):

Если нет - кто мешает?

Кто Вам мешает - не знаю. Мне никто не помешал. Я запустил программу Mathematica 5.1, написал две формулы
$\mathrm{PrPi[k\_Integer]:=k-1+\sum\limits_{j=1}^kFloor\left[\frac 2j\left(1+\sum\limits_{s=1}^{Floor[\sqrt{j}]}\left(Floor\left[\frac{j-1}s\right]-Floor\left[\frac js\right]\right)\right)\right]}$
и
$\mathrm{P[n\_Integer]:=1+\sum\limits_{k=1}^{2Floor[n\,Log[n]+1]}\left(1-Floor\left[\frac{PrPi[k]}n\right]\right)}$
приведённые по указанной Jnrty ссылке, а потом вычислял:
$\mathrm{Timing[PrPi[1000]]}$
{0.171 Second, 168}
$\mathrm{Timing[PrPi[10000]]}$
{4.578 Second, 1229}
Встроенная функция PrimePi работает быстрее:
$\mathrm{Timing[PrimePi[10000]]}$
{0.015 Second, 1229}
А теперь - вычисление 168-го простого числа:
$\mathrm{Timing[P[168]]}$
{236.422 Second, 997}
Если заменить функцию PrPi встроенной функцией PrimePi, получится гораздо быстрее:
{0.063 Second, 997}
Ещё быстрее получится, если использовать встроенную функцию Prime:
$\mathrm{Timing[Prime[1000000000]]}$
{0. Second, 22801763489}
$\mathrm{Timing[Prime[10000000000]]}$
{1.625 Second, 252097800623}

[Droog_Andrey]

serval в сообщении #393524 писал(а):

Этим способом можно получить конкретное заведомо простое число?

Да.

[Droog_Andrey]

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

SerjeyMinsk в сообщении #393103 писал(а):

Есть ли в математике вообще такая проблема как отсутствие закономерности в распределении простых чисел на сегодняшний день? Или её нет?

Такой проблемы нет. В распределении простых чисел присутствует множество закономерностей.

Кстати, наличие этих закономерностей (при крупномасштабном рассмотрении) имеет ту же природу, что существование музыкальных шкал равномерной темперации (вроде современной 12-ступенной шкалы).