Быстрый алгоритм для поиска числа простых чисел между двумя номерами

Question

Моя проблема сводится к поиску количества простых чисел между двумя заданными числами. Я мог бы иметь диапазон, равный 1 to (1000)!, и, следовательно, мне нужны некоторые математические оптимизации.

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

P.S: Это определенно похоже, что я, возможно, достиг тупика, но все, что я ищу, - это некоторые оптимизации, которые могли бы помочь в решении этого. А также я ищу только однопоточный подход.

EDIT: Один из подходов, о котором я думал и могу решить множество проблем, связанных с большим простым числом, - это для кого-то поддерживать глобальную таблицу простых чисел и сделать ее доступной для поиска. Люди в проекте PrimeGrid могут внести полезный вклад в это.

Answer 1

Поскольку вы хотите пойти до 1000! (factorial). Вы не сможете получить точные результаты с помощью известных в настоящее время методов по текущей технологии.

Prime Counting Function оценивается только для нескольких значений до 10^24. Таким образом, вы не сможете ударить 1000!.

---

Но так как вы упоминаете, чем приближение может быть хорошо, вы можете использовать Logarithmic Integral как приближение к премьеру считающей функции.

Это основано на Prime Number Theorem, в котором говорится, что функция Prime Counting асимптотична для логарифмического интеграла.

Answer 2

Самый быстрый способ, который я знаю, заключается в том, чтобы устранить все известные простые числа (четные числа, все числа с делителями ниже начального числа в диапазоне и т. Д.) Так быстро, как вы можете, а затем перебрать остальное и используйте что-то вроде Euclidean algorithm, чтобы определить, является ли это число простым.

Answer 3

Вы можете обследовать свои варианты здесь: http://en.wikipedia.org/wiki/Prime_counting_function

Это также выглядит полезным: http://mathworld.wolfram.com/PrimeCountingFunction.html

Могу ли я узнать, почему вам это нужно до 1000! ? Похоже, никто никогда не считал, что многие раньше. Имеются 1 925 320 209, 696 803 968 923 простых числа от 1 до 10^23. 1000! = 10^120. Мне сейчас интересно.

Answer 4

Существует fast, simple approximation количеству простых чисел, указанных ниже. Если вам не нужны точные значения, то разница в двух оценках этой формулы поможет вам приблизиться.

Answer 5

Простой алгоритм подсчета, разработанный Lagarias и другими, цитируемый другими, проходит очень грубо в O (n^(2/3)). Поскольку сито для простых чисел от k1 до k2 принимает приблизительно O (max (sqrt (k2), k2 - k1), вы должны проверить, насколько далеко ваши нижние и верхние границы отделены друг от друга, либо либо сито, либо использовать алгоритм подсчета , в зависимости от того, что будет быстрее.

BTW. Алгоритм простого подсчета может быть настроен для подсчета простых чисел от 1 до n для различных значений n, которые разумно близки друг к другу быстрее, чем подсчет их по отдельности.(В принципе, он выбирает число N, создает сито размером n/N и просматривает значения N^2 в этом сите. O (n^(2/3)) исходит из того, что при N = n^(1/3) обе операции принимают шаги N^(2/3). Это сито может быть повторно использовано для разных n, но нужно искать разные значения. Таким образом, для k разных значений n вы делаете N немного меньше, увеличивая стоимость сита (только один раз), но уменьшая стоимость поиска (k раз)).

Для n около 1000 !, нет никаких шансов. Вы даже не можете подсчитать количество простых чисел в [n, n] для значений этого размера, если n не имеет маленьких (ish) факторов.