Учитывая число X, оцените, где в упорядоченном списке простых чисел это число может упасть

Question

Учитывая заранее вычисленный упорядоченный список простых чисел и предоставленное число X, я хочу приблизительно оценить, где X попадет в список простых чисел, и начать поиск с этой точки.

Итак, явычислили и сохранили список простых чисел из 1..2 ^ 32-1 в двоичном файле.У меня есть методы в программе, которая работает с этим файлом, чтобы получить n-е простое число, случайное простое число, сколько простых чисел существует и т. Д. Но для того, чтобы добавить функцию в эту программу, чтобы сказать мне, где поставленное число является простымЯ не могу придумать способ, с чего начать поиск.Выполнение этого наивного метода O (n) быстро становится невозможным даже для чисел <2 ^ 32. </p>

Я пробовал теорему о простых числах (x / ln x) и проводил исследования в некоторых других областях,но я не совсем нашел правильное распределение, и я боюсь, что моя теория чисел не на высоте.

Я ищу что-то вроде, например,

1 2 3 4  5  6 .. 100 ..  500 .. 1000 ..  5000 ..  10000
2 3 5 7 11 13 .. 541 .. 3571 .. 7919 .. 48611 .. 104729

lookup (13) даст мне число рядом, но <= 6, lookup (7920) даст мне число <= 1000, а lookup (104729) даст число <= 10000 и т. д. </p>

PS Я понимаю, что это глупый метод по нескольким причинам: а) я мог хранить его по-другому и иметь O (1) поиск;б) я мог бы существенно сжать хранилище;c) для таких небольших чисел я мог бы выполнить простое тестирование данного числа во время выполнения, полностью пропустить таблицу поиска, и это было бы быстрееЯ не заинтересован в решении этих проблем ;Я искренне хочу знать, существует ли проверенный метод оценки того, где в отсортированном списке простых чисел данное число может упасть .Следовательно, это скорее вопрос математики / теории чисел, чем вопрос реализации.

PPS Это не домашняя работа.

PPPS Я провел довольно тщательный поиск в StackOverflow, но, возможно, пропустил прямойОтветьте на это.

Спасибо.

Answer 1

Число простых чисел, меньших x, приблизительно равно логарифмическому интегралу x, li (x).Обращение функции * дает очень хорошую оценку того, насколько велико k-е простое число.

Если вы хотите избежать программирования логарифмического интеграла, разумное приближение составляет

k ln n + k ln ln k - k

После просмотра значения в этой точке вВ таблице вы можете оценить правильное положение еще более точно, используя плотность простых чисел в этой точке.Поэтому, если вы хотели получить миллионное простое число и оценили его в 15 502 175, но обнаружили, что ближайший простое число в этой точке составляет 1 001 000 тысяч, вы можете переоценить миллионное простое число как старую оценку - 1000 ln (15502175).1018 ** Технически, функция не является биективной и, следовательно, не обратимой, но ее достаточно легко инвертировать в интересующий вас регион, скажем, x> = 2.

Answer 2

http://en.wikipedia.org/wiki/Prime_number#Number_of_prime_numbers_below_a_given_number на помощь.

Answer 3

Поправьте меня, если я неправильно понял вопрос, но разве простой бинарный поиск не нашел нужную пару в упорядоченном списке?