Решение, содержит ли интервал простое число

В чем сложность определения, содержит ли интервал натуральных чисел простое число? Вариант решета Эратосфена дает алгоритм, где является длина интервала и Шкуры поли-логарифмические факторы в исходной точке интервала; мы можем сделать лучше (с точки зрения только)? $\tilde O(L)$ $L$ $\sim$ $L$

cc.complexity-theory ds.algorithms nt.number-theory comp-number-theory Эллиот Гороховский
источник

Nitpick: Сито Эратосфена не дает вам просто полилогарифмические факторы в начальной точке, даже для интервала длины 1. Действительно, можно проверить, что число простое - это время, которое является полилогарифмическим в числе (= полиномиальный по размеру представления), но для этого требуется алгоритм, намного более сложный, чем сито Эратосфена.

Ванесса

@Squark True, должен был указывать «псевдослучайность относительно заданной факторной базы». Хотя по мере того, как начальная точка интервала становится большой, ожидаемая стоимость тестирования простоты сводится к нулю ...

Эллиот Гороховский

Отказ от ответственности : я не эксперт в теории чисел.

Краткий ответ : если вы хотите принять «разумные теоретико-числовые гипотезы», то мы можем сказать, существует ли простое число в интервале во времени . Если вы не готовы сделать такое предположение, то есть красивый алгоритм из - за Odlyzko , который достигает , и я считаю , что это самый известный. $[n, n+\Delta]$ $\mathrm{polylog}(n)$ $n^{1/2 + o(1)}$

Очень полезная ссылка с множеством полезной информации о тесно связанной проблеме : проект PolyMath по детерминированным алгоритмам для поиска простых чисел .

Длинный ответ :

Это сложная проблема, активная область исследований, и, похоже, она тесно связана с трудным вопросом о границе между простыми числами. С моральной точки зрения ваша проблема очень похожа на проблему определения простого числа между и , которая недавно была предметом проекта PolyMath . (Если вы хотите действительно углубиться в эти вопросы, эта ссылка - отличное место для начала.) В частности, наши лучшие алгоритмы для обеих задач по сути одинаковы. $n$ $2n$

В обоих случаях лучший алгоритм сильно зависит от размера промежутков между простыми числами. В частности, если таково, что всегда есть простое число между и (и может быть эффективно вычислено), то мы всегда можем найти простое число во времени следующим образом. Чтобы определить, есть ли простое число между и $f(n)$ $n$ $n + f(n)$ $f(n)$ $\mathrm{polylog}(n) \cdot f(n)$ $n$ , сначала проверьте, если . Если так, выведите да. В противном случае, просто переберите целые числа между и и проверьте каждый на предмет простоты, и ответьте «да», если найдете простое число, и «нет» в противном случае. (Это можно сделать детерминистически, поэтому детерминистическое нахождение простого числа между и так тесно связано с определением, есть ли простое число в определенном интервале.) $n + \Delta$ $\Delta \geq f(n)$ $n$ $n + \Delta$ $n$ $2n$

$\mathrm{polylog}(n)$ $f(n) = O(\log^2 n)$ $n \geq 3$ $1/\log n$

$f(n) \leq O(\sqrt{n})$ $f(n) \leq O(\sqrt{n} \log n)$ $n^{o(1)}$

$\widetilde{O}(n^{0.525})$ $n^{0.025}$

Ной Стивенс-Давидович
источник

k

$k$

k

$k$ это заданное число? И какова сложность в этом случае?

Майкл Вехар

@MichaelWehar Хороший вопрос. Алгоритм Одлызко определенно может, так как его алгоритм фактически вычисляет функцию простого подсчета

π (x) := \# primes below \leq x

$\pi(x) := \text{\# primes below $\leq x$}$ , Для подхода, использующего промежутки между простыми числами, я не тот парень, которого нужно спрашивать. Очевидно, что это требует ограничений на

p_{n + k} - p_{n}

$p_{n+k}-p_n$ в отличие от всего

p_{n + 1} - p_{n}

$p_{n+1}-p_n$ и я просто не знаю много об этом. Может кто еще знает?

Ноа Стивенс-Давидович

Решение, содержит ли интервал простое число

Ответы: