Есть ли способ найти приблизительное значение n-го простого числа?
https://stackoverflow.com/questions/1042717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Существует ли функция, которая вернет приблизительное значение n й премьер?Я думаю, это было бы что-то вроде приблизительной обратной функции подсчета простых чисел.Например, если бы я дал этой функции 25, она вернула бы число около 100, или если бы я дал этой функции 1000, она вернула бы число около 8000.Меня не волнует, является ли возвращаемое число простым или нет, но я хочу, чтобы оно было быстрым (поэтому не генерируйте первое n простые числа, возвращающие n й.)
Я хотел бы этого, чтобы я мог сгенерировать первый n простые числа с помощью сита (Эратосфен или Аткин).Следовательно, аппроксимация для n в идеале никогда не следует недооценивать ценность фактического n первое число.
(Обновление:видишь мой ответ для хорошего метода нахождения верхней границы 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-битного ввода и быть на порядок или более ближе, чем формула из Robin, приведенная ранее (или сложная формула Wimblik с ограниченным диапазоном).Для моего использования у меня есть немного большая таблица малых простых чисел, поэтому я могу немного ужесточить последнюю оценку.Технически, исходя из формул, мы могли бы использовать floor() вместо ceil (), но я беспокоюсь о точности.
Редактировать:Другим вариантом для некоторого улучшения этого является реализация хороших границ количества простых чисел (напримерAxler 2014) и выполняет по ним бинарный поиск.Мой код для этого метода занимает в ~ 10 раз больше времени, чем приведенный выше (все еще выполняется менее чем за миллисекунду), но может уменьшить процент ошибок на порядок.
Если вам нужна оценка для n-го простого числа, вы можете сделать:
- Чиполла 1902 (см. Дусарт 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 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 функцию простого приближения, чтобы использовать второе приближение для 6 <= n < 7022, первое приближение для <=> и поиск в массиве для первых 5 простых чисел.
(Хотя первый метод не является очень жестким ограничением, особенно для диапазона, в котором я его использую, меня это не беспокоит, так как я хочу это для сита, а сито с меньшими числами вычислительно дешево.)
Теорема простых чисел дает число простых чисел ниже порогового значения, поэтому оно может быть используется, чтобы дать приблизительное значение для n-го простого числа.
В качестве приблизительной оценки вы можете использовать n * ln (n) в качестве аппроксимации для n-го простого числа. Существует гораздо более сложный, но более точный метод, подробности которого вы можете найти в Википедии здесь .
My Best Prime (n) Estimate
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)))))))
Эффективная реализация, вероятно, невозможна при использовании сита. Подумайте, что произойдет, если вы захотите получить первые 10.000 простых чисел. Возможно, вам придется просеять огромное количество цифр.
Ваш собственный вклад в этот вопрос и my answer - это хорошие способы реализовать это, не зная appr. значение простого числа
Чтобы дополнить верхнюю границу Даны Дж, эта формула должна дать вам хорошую нижнюю границу.
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;
