Есть ли способ найти приблизительное значение n-го простого числа?

Question

Есть ли функция, которая будет возвращать приблизительное значение n -го простого числа? Я думаю, что это было бы что-то вроде приближенной обратной функции подсчета простых чисел. Например, если бы я дал эту функцию 25, она вернула бы число около 100, или если бы я дал эту функцию 1000, она вернула бы число около 8000. Мне все равно, простое ли возвращенное число или нет, но я хочу это должно быть быстро (поэтому не нужно генерировать первые n простых чисел для возврата n th.)

Мне бы хотелось, чтобы я мог сгенерировать первые n простых чисел, используя сито ( Eratosthenes или Atkin ). Следовательно, приближение для n th в идеале никогда не должно недооценивать значение фактического n th простого числа.

(Обновление: см. мой ответ для хорошего метода нахождения верхней границы n th простого числа.)

Answer 1

Более узкие границы:

static const unsigned short primes_small[] = {0,2,3,5,7,11};

static unsigned long nth_prime_upper(unsigned long n) {
  double fn = (double) n;
  double flogn, flog2n, upper;
  if (n < 6)  return primes_small[n];
  flogn  = log(n);
  flog2n = log(flogn);

  if      (n >= 688383)    /* Dusart 2010 page 2 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn));
  else if (n >= 178974)    /* Dusart 2010 page 7 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));
  else if (n >=  39017)    /* Dusart 1999 page 14 */
    upper = fn * (flogn + flog2n - 0.9484);
  else                    /* Modified from Robin 1983 for 6-39016 _only_ */
    upper = fn * ( flogn  +  0.6000 * flog2n );

  if (upper >= (double) ULONG_MAX) {
     /* Adjust this as needed for your type and exception method */
    if (n <= 425656284035217743UL) return 18446744073709551557UL;
    fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1);
  }

  return (unsigned long) ceil(upper);
}

Они не должны быть меньше фактического значения nth_prime, должны работать для любого 64-битного ввода и быть на порядок или более ближе, чем формула Робина, приведенная ранее (или сложная формула Вимблика с ограниченным диапазоном). Для моего использования у меня есть немного большая таблица небольших простых чисел, так что я могу немного уточнить последнюю оценку. Технически из формул мы могли бы использовать floor () вместо ceil (), но я беспокоюсь о точности.

Редактировать: Еще одна возможность немного улучшить это - реализовать хорошие границы простого числа (например, Axler 2014) и выполнить двоичный поиск по ним. Мой код для этого метода занимает ~ 10 раз дольше, чем выше (все еще работает менее миллисекунды), но может уменьшить процент ошибок на порядок.

Если вы хотите получить оценку для n-го простого числа, вы можете сделать:

• Cipolla 1902 (см. Dusart 1999 стр. 12 или этот документ . Я считаю полезными три члена (m = 2) плюс поправочный коэффициент третьего порядка, но с большим количеством условий он колеблется слишком сильно. Формула, показанная в ссылке на Википедию, является этой формулой (с m = 2). Использование двухчленного обратного li или обратного Римана R ниже даст лучшие результаты.
• Рассчитайте верхнюю и нижнюю границы Dusart 2010 и усредните результаты. Не так уж и плохо, хотя я подозреваю, что использование взвешенного среднего значения будет работать лучше, поскольку границы не одинаково тесны.
• li ^ {- 1} (n) Поскольку li (n) является приличным приближением к простому числу, обратное является приличным приближением nth_prime. Это, и все остальное, может быть сделано довольно быстро, как двоичный поиск по функции.
• li ^ {- 1} (n) + li ^ {- 1} (sqrt (n)) / 4 Ближе, так как это приближается к R (n)
• R ^ {- 1} Обратная функция Римана R является ближайшим средним приближением, которое я знаю, это разумно.

Наконец, если у вас есть очень быстрый метод подсчета простых чисел, такой как одна из реализаций LMO (сейчас есть три реализации с открытым исходным кодом), вы можете написать быстрый точный метод nth_prime. Вычисление 10 ^ 10-го простого числа может быть сделано за несколько миллисекунд, а 10 ^ 13-го за пару секунд (на современной быстрой машине). Аппроксимации очень быстрые при любых размерах и работают для гораздо больших чисел, но у каждого есть другое представление о том, что означает «большой».

Answer 2

Спасибо за все эти ответы. Я подозревал, что было что-то довольно простое, но я не мог найти это в то время. Я тоже провел немного больше исследований.

Поскольку я хочу, чтобы сито генерировало первые n простые числа, я хочу, чтобы аппроксимация была больше или равна n th премьер. (Поэтому я хочу верхнюю границу n th простого числа.)

Википедия дает следующую верхнюю оценку для n >= 6

p_n <= n log n + n log log n   (1)

, где p_n - это n -ое простое число, а log - натуральный логарифм. Это хорошее начало, но его можно переоценить на немалую сумму. Эта статья в Журнале математики колледжа дает более жесткую верхнюю границу для n >= 7022

p_n <= n log n + n (log log n - 0.9385)   (2)

Это намного более жесткий предел, как показано в следующей таблице

n         p_n         approx 1    error%  approx 2    error%
1         2                            
10        29          31          6.90 
100       541         613         13.31
1000      7919        8840        11.63
10000     104729      114306      9.14    104921      0.18
100000    1299709     1395639     7.38    1301789     0.16
1000000   15485863    16441302    6.17    15502802    0.11
10000000  179424673   188980382   5.33    179595382   0.10

Я реализовал свою n функцию простого приближения, чтобы использовать второе приближение для n >= 7022, первое приближение для 6 <= n < 7022 и поиск в массиве для первых 5 простых чисел.

(Хотя первый метод не является очень жестким ограничением, особенно для диапазона, в котором я его использую, меня это не беспокоит, так как я хочу это для сита, а сито с меньшими числами вычислительно дешево.)

Answer 3

В качестве приблизительной оценки вы можете использовать n * ln (n) в качестве аппроксимации для n-го простого числа. Существует гораздо более сложный, но более точный метод, подробности о котором вы можете найти в Википедии здесь .

Answer 4

Теорема простых чисел дает число простых чисел ниже порогового значения, поэтому его можно использовать для получения приблизительного значения для n-го простого числа.

Answer 5

My Best Prime (n) Эстимейт

1/2*(8-8.7*n-n^2+
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2))))))

Вот моя последняя экспериментальная формула. Кстати. Десять триллионных простых чисел равны 323,780,508,946,331, эта формула работает достаточно хорошо в этом масштабе, не будучи уверенным в том, что она продолжает приближаться к n*ln(n)+n*(ln(ln(n))-0.9385).

1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))*
ln(ln((n*ln(8*n))/ln(n))/ln(2)))))))

Answer 6

Чтобы дополнить верхнюю границу Даны Дж, эта формула должна дать вам хорошую нижнюю границу.

P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;

Answer 7

Эффективная реализация, вероятно, невозможна с ситом. Подумайте, что произойдет, если вы захотите получить первые 10.000 простых чисел. Вы, вероятно, должны были бы сделать сито над огромным большим количеством чисел.

Ваш собственный смысл в этом вопросе и мой ответ являются хорошими способами реализовать это, не зная подтверждения. значение простого числа