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

Более узкие рамки:

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-битного ввода и быть на порядок или более близкими, чем формула Робина, приведенная ранее (или сложная формула Wimblik с ограниченным диапазоном). Для моего использования у меня есть таблица малых простых чисел немного большего размера, так что я могу немного уточнить последнюю оценку. Технически из формул мы могли бы использовать 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-го - за пару секунд (на современной быстрой машине). Приближения очень быстрые для всех размеров и работают для гораздо больших чисел, но каждый по-своему понимает, что означает «большой».

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

Поскольку я хочу, чтобы сито генерировало первое n < / em> простые числа, я хочу, чтобы приближение было больше или равно n -ому простому числу. (Следовательно, мне нужна верхняя граница n -го простого числа.)

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

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