Gibt es eine Möglichkeit den ungefähren Wert des n-ten Primzahl zu finden?
https://stackoverflow.com/questions/1042717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Gibt es eine Funktion, die den ungefähren Wert des kehrt n th prime? Ich denke, das so etwas wie eine aherungsinverse Primzahlfunktion wäre. Zum Beispiel würde, wenn ich diese Funktion 25 gab es eine Reihe rund 100 zurückzukehren, oder wenn ich diese Funktion 1000 gab es wäre eine Zahl um 8000. kehre ich mich nicht, wenn die zurückgegebene Zahl prim ist oder nicht, aber ich will es schnell zu sein (so die ersten keine Erzeugung von n Primzahlen zurück die n th.)
Ich würde dies gerne so, dass ich die erste erzeugen kann n Primzahlen unter Verwendung eines Siebs ( Eratosthenes oder Atkin ). Daher ist die Näherung für n th die idealerweise nie den Wert der tatsächlichen unterschätzen n th Primzahl ist.
(Update: siehe meine Antwort für eine gute Methode zu finden, die Obergrenze des n th Primzahl.)
Lösung
Engere Grenzen:
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);
}
Diese sollten immer nicht kleiner sein als die tatsächliche nth_prime, sollte für jeden 64-Bit-Eingang arbeiten, und eine Größenordnung oder mehr näher als die Formel von Robin gegeben früher (oder Wimblik des komplizierten Bereich begrenzte Formel). Für meinen Einsatz habe ich eine etwas größere kleine Primzahlen Tabelle so kann die letzte Schätzung etwas mehr verschärfen. Technisch aus den Formeln konnten wir Boden () anstelle von ceil (), aber ich mache mir Sorgen um Präzision.
Edit: Eine weitere Möglichkeit zur Verbesserung dieses etwas ist gut prime Zahl Grenzen der Umsetzung (z Axler 2014) und auf ihnen eine binäre Suche zu tun. Mein Code für diese Methode dauert ~ 10x länger als die oben (noch unter einer Millisekunde ausgeführt wird), kann aber die Fehlerquote durch eine Größenordnung reduzieren.
Wenn Sie eine Schätzung für die n-te Primzahl möchten, können Sie tun:
- Cipolla 1902 (siehe Dusart 1999 Seite 12 oder dieses Papier . ich finde, drei Terme (m = 2) und ein dritte Ordnung Korrekturfaktor nützlich zu sein, aber mit mehr Begriffen es zu viel oszilliert. die Formel in den Empfehlungen dargestellt ist diese Formel (mit m = 2). Unter Verwendung der beide Zeit invers li oder inverse Riemann R unten bessere Ergebnisse geben.
- Berechnen Sie die Dusart 2010 obere und untere Grenze und die Ergebnisse gemittelt. Gar nicht so schlecht, obwohl ich vermute, ein gewichtetes Mittel verwendet wird besser funktionieren als die Grenzen sind nicht gleichmäßig fest.
- Li ^ {- 1} (n) Da Li (n) ist eine annehmbare Annäherung an die Anfangszahl, ist die inverse eine annehmbare Approximation nth_prime. Dies und der ganze Rest kann ziemlich schnell als eine binäre Suche auf die Funktion durchgeführt werden.
- li ^ {- 1} (n) + li ^ {- 1} (sqrt (n)) / 4 Näher, da dies immer näher an R (n)
- R ^ {- 1}. Die inverse Riemann R-Funktion ist die nächste mittlere Annäherung ich weiß, das ist vernünftig
Schließlich, wenn Sie eine sehr schnelle prime Zählverfahren wie einer der LMO-Implementierungen haben (es gibt drei Open-Source-Implementierungen jetzt), können Sie eine schnelle präzise nth_prime Methode schreiben. 10. prime die Berechnung der 10 ^ kann in wenigen Millisekunden erfolgen, und die 10 ^ 13 in ein paar Sekunden (auf einer modernen schnellen Maschine). Die Annäherungen sind extrem schnell in allen Größen und für weit größere Zahlen arbeiten, aber jeder hat eine andere Vorstellung davon, was „großer“ bedeutet.
Andere Tipps
Vielen Dank für all die Antworten. Ich vermuten, es war etwas ziemlich einfach so, aber ich konnte es nicht an der Zeit finden. Ich habe auch ein bisschen mehr Forschung getan.
Wie ich es für einen Sieb die erste zu erzeugen n Primzahlen, möchte ich die Annäherung als oder gleich th prim zu dem n größer sein. (Aus diesem Grund möchte ich die obere Grenze des n th Primzahl.)
Wikipedia die folgende obere Schranke für n >= 6 gibt
p_n <= n log n + n log log n (1)
wo p_n ist die n th prime und log der natürliche Logarithmus ist. Dies ist ein guter Anfang, aber es kann durch einen nicht unerheblichen Betrag überschätzt. Dieser Artikel in The College Mathematik Journal gibt eine engere Obergrenze für n >= 7022
p_n <= n log n + n (log log n - 0.9385) (2)
Dies ist eine viel engere gebunden, wie die folgende Tabelle zeigt
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
I umgesetzt mein n th prime Approximationsfunktion die zweite Näherung für n >= 7022, die in erster Näherung für 6 <= n < 7022, und ein Array-Lookup für die ersten 5 Primzahlen zu verwenden.
(Obwohl die erste Methode ist nicht sehr fest gebunden, vor allem für den Bereich, in dem ich es verwenden, ich bin nicht besorgt, wie ich dies für ein Sieb werden soll, und ein Sieb mit einem kleineren Anzahl ist rechnerisch billig.)
Primzahltheorems eine Anzahl von Primzahlen unter einen Schwellenwert gibt, soll es so sein könnte verwendet, um einen Näherungswert für den n-te Primzahl zu geben.
Als grobe Schätzung, können Sie n * ln (n) als Näherung für den n-te Primzahl verwenden. Es gibt eine viel komplexere, aber genauere Methode, deren Einzelheiten Sie auf Wikipedia finden hier .
My Best Prime (n) Schätzung
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))))))
Hier ist meine neueste experimentelle Formel.
btw. Die 10000000000000. Primzahl ist 323,780,508,946,331 diese Formel funktioniert recht gut an, dass die Skala nicht sicher, ob es weiterhin als n*ln(n)+n*(ln(ln(n))-0.9385) näher zu kommen.
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)))))))
Eine effiziente Implementierung ist wahrscheinlich mit einem Sieb nicht möglich. Denken Sie, was passieren würde, wenn man die ersten 10.000 Primzahlen haben wollen. Sie würden wahrscheinlich ein Sieb über eine riesige größere Menge von Zahlen machen.
Ihre eigene implentation in diese Frage und my beantworten gute Möglichkeiten, dies zu implementieren, ohne die ca. zu kennen. Wert eines Strichs
Dana J Upper Zur Ergänzung gebunden sollte diese Formel gibt Ihnen eine gute untere Schranke.
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;
