Existe-t-il un moyen de trouver la valeur approximative du nième nombre premier?
https://stackoverflow.com/questions/1042717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Existe-t-il une fonction qui renvoie la valeur approximative du n e prime? Je pense que ce serait quelque chose comme une fonction approximative de comptage inverse approximative. Par exemple, si je donnais cette fonction à 25, il retournerait un nombre autour de 100, ou si je donnais cette fonction à 1000, il me renverrait un nombre autour de 8000. Peu m'importe si le nombre retourné est premier ou pas, mais je veux il doit être rapide (donc ne pas générer les premiers n nombres premiers pour renvoyer le n e).
Je voudrais ceci afin de pouvoir générer les premiers n nombres à l'aide d'un tamis ( Eratosthenes ou Atkin ). Par conséquent, l’approximation pour n th ne devrait idéalement jamais sous-estimer la valeur de la n valeur réelle.
(Mise à jour: voir ma réponse est une bonne méthode pour trouver la limite supérieure du n ème nombre premier.)
La solution
Resserrement des limites:
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);
}
Celles-ci ne devraient jamais être inférieures au nth_prime réel, devraient fonctionner pour toute entrée 64 bits et être d'un ordre de grandeur ou plus proches de la formule de Robin donnée précédemment (ou de la formule compliquée à plage limitée de Wimblik). Pour mon usage, j'ai une petite table de nombres premiers légèrement plus grande donc je peux resserrer un peu plus la dernière estimation. Techniquement, à partir des formules, nous pourrions utiliser floor () au lieu de ceil () mais je me soucie de la précision.
Modifier: Une autre option pour améliorer un peu ce problème consiste à implémenter de bonnes limites de comptage (par exemple, Axler 2014) et à effectuer une recherche binaire sur celles-ci. Mon code pour cette méthode prend environ 10 fois plus longtemps que la précédente (il ne tourne toujours qu’en une milliseconde), mais peut réduire le pourcentage d’erreur d’un ordre de grandeur.
Si vous voulez une estimation pour le nième nombre premier, vous pouvez faire:
- Cipolla 1902 (voir Dusart 1999 page ou cet article . Je trouve trois termes (m = 2) plus un facteur de correction du troisième ordre pour être utiles, mais avec plus de termes, le nombre de mots oscille trop. La formule indiquée dans le lien Wikipedia est la formule suivante (avec m = 2). ou inverse Riemann R ci-dessous donnera de meilleurs résultats.
- Calculez les limites supérieure et inférieure de Dusart 2010 et faites la moyenne des résultats. Pas si mal que ça, mais je pense que l’utilisation d’une moyenne pondérée donnera de meilleurs résultats, car les limites ne sont pas aussi serrées.
- li ^ {- 1} (n) Puisque li (n) est une approximation décente du compte de nombres premiers, l'inverse est une approximation de nth_primes décente. Ceci, et tout le reste, peut être fait assez rapidement comme une recherche binaire sur la fonction.
- li ^ {- 1} (n) + li ^ {- 1} (sqrt (n)) / 4 Plus proche, puisque cela se rapproche de R (n)
- R ^ {- 1} La fonction inverse de Riemann R est l'approximation moyenne la plus proche, je sais que c'est raisonnable.
Enfin, si vous avez une méthode de décompte initiale très rapide telle que l’une des implémentations de LMO (il existe trois implémentations open source), vous pouvez écrire une méthode nth_prime rapide et précise. Le calcul du 10 ^ 10e prime peut être effectué en quelques millisecondes et le 10 ^ 13 en quelques secondes (sur une machine rapide moderne). Les approximations sont extrêmement rapides pour toutes les tailles et fonctionnent pour des nombres beaucoup plus grands, mais tout le monde a une idée différente de ce que & "Grand &"; signifie.
Autres conseils
Merci pour toutes ces réponses. Je pensais qu'il y avait quelque chose d'assez simple comme ça, mais je ne pouvais pas le trouver à ce moment-là. J'ai aussi fait un peu plus de recherches.
Comme je le souhaite pour un sieve pour générer le premier n nombres premiers, je veux que l'approximation soit supérieure ou égale au n e nombre premier. (Par conséquent, je veux la limite supérieure du n ème nombre premier.)
Wikipedia indique la limite supérieure suivante pour n >= 6
p_n <= n log n + n log log n (1)
où p_n est le n ème nombre et log le logarithme naturel. C'est un bon début, mais il est possible de surestimer un montant non négligeable. Cet article dans Le College Mathematics Journal fixe une limite supérieure plus étroite pour n >= 7022
p_n <= n log n + n (log log n - 0.9385) (2)
Il s'agit d'une limite beaucoup plus étroite, comme le montre le tableau suivant
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
J'ai implémenté ma n ème approximation pour utiliser la deuxième approximation de 6 <= n < 7022, la première approximation de <=>, ainsi qu'une recherche de tableau pour les 5 premiers nombres premiers.
(Bien que la première méthode ne constitue pas une limite très étroite, en particulier pour la gamme dans laquelle je l’utilise, je ne suis pas concernée car je le souhaite pour un tamis, et un tamis de nombres plus petits est économiquement économique.)
le théorème des nombres premiers donne un nombre de nombres premiers inférieur à une valeur seuil, de sorte qu'il peut être utilisé pour donner une valeur approximative pour le nième nombre premier.
Comme estimation approximative, vous pouvez utiliser n * ln (n) comme approximation du nième nombre premier. Il existe une méthode beaucoup plus complexe, mais plus précise, dont vous pouvez trouver les détails sur Wikipedia ici .
Estimation de mon meilleur premier prix
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))))))
Voici ma formule la plus récente, la plus expérimentale.
btw. Le dix milleième de prime est 323,780,508,946,331 cette formule fonctionne assez bien à cette échelle-là, elle ne sait pas si elle continue à se rapprocher de 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)))))))
Une mise en oeuvre efficace n’est probablement pas possible avec un tamis. Pensez à ce qui arriverait si vous voulez avoir les 10 000 premiers nombres premiers. Vous auriez probablement à faire un tamis sur un plus grand nombre de chiffres.
Votre propre implémentation dans cette question et my answer sont de bons moyens pour implémenter cette tâche sans connaître le résultat. valeur d'un nombre premier
Pour compléter la limite supérieure de Dana J, cette formule devrait vous donner une bonne limite inférieure.
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;
