Есть ли способ найти приблизительное значение n-го простого числа?
Есть ли функция, которая будет возвращать приблизительное значение n- го простого числа? Я думаю, что это было бы что-то вроде приближенной обратной функции подсчета простых чисел. Например, если бы я дал эту функцию 25, она вернула бы число около 100, или если бы я дал эту функцию 1000, она вернула бы число около 8000. Мне все равно, простое ли возвращенное число или нет, но я хочу это должно быть быстро (поэтому не нужно генерировать первые n простых чисел для возврата n- го.)
Мне бы хотелось, чтобы я мог сгенерировать первые n простых чисел, используя сито ( Эратосфен или Аткин). Следовательно, приближение для n- го числа в идеале никогда не должно недооценивать значение фактического n- го простого числа.
(Обновление: см. Мой ответ для хорошего метода нахождения верхней границы n- го простого числа.)
7 ответов
Более жесткие границы:
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-го за пару секунд (на современной быстрой машине). Аппроксимации очень быстрые при любых размерах и работают для гораздо больших чисел, но у каждого есть другое представление о том, что означает "большой".
Спасибо за все эти ответы. Я подозревал, что было что-то довольно простое, но я не мог найти это в то время. Я тоже провел немного больше исследований.
Поскольку я хочу, чтобы сито генерировало первые n простых чисел, я хочу, чтобы аппроксимация была больше или равна n- му простому числу. (Поэтому я хочу верхнюю границу n- го простого числа.)
Википедия дает следующую верхнюю оценку для n >= 6
p_n <= n log n + n log log n (1)
где p_n это n- е простое число, и log натуральный логарифм Это хорошее начало, но его можно переоценить на немалую величину. Эта статья в The College Matmatics Journal дает более строгую оценку 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 простых чисел.
(Хотя первый метод не является очень жестким ограничением, особенно для диапазона, в котором я его использую, меня это не беспокоит, так как я хочу это для сита, а сито с меньшим числом является вычислительно дешевым.)
Теорема простых чисел дает число простых чисел ниже порогового значения, поэтому ее можно использовать для получения приблизительного значения для n-го простого числа.
В качестве приблизительной оценки вы можете использовать n*ln(n) в качестве аппроксимации для n-го простого числа. Существует гораздо более сложный, но более точный метод, подробности о котором вы можете найти в Википедии здесь.
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)))))))
Чтобы дополнить верхнюю границу Даны Дж, эта формула должна дать вам хорошую нижнюю границу.
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;
Эффективная реализация, вероятно, невозможна при использовании сита. Подумайте, что произойдет, если вы захотите получить первые 10.000 простых чисел. Вы, вероятно, должны были бы сделать сито по огромному большему количеству чисел.
Ваш собственный вклад в этот вопрос и мой ответ являются хорошими способами реализовать это, не зная одобрения. значение простого