Y a-t-il un moyen de trouver la valeur approximative du nième prime?

Est-il une fonction qui renvoie la valeur approximative de la n e premier? Je pense que ce serait quelque chose comme une approximation inverse premier la fonction de compte. Par exemple, si j'ai donné cette fonction 25, il serait de retour à un nombre de l'ordre de 100, ou si j'ai donné cette fonction 1000, il serait de retour à un nombre de l'ordre de 8000. Je n'ai pas de soins si le nombre retourné est premier ou pas, mais je ne veux pas qu'il soit rapide (donc pas de la génération de la première n des nombres de la prime de retour à l' n th.)

Je voudrais ce que je puisse générer le premier n nombres premiers à l'aide d'un tamis (Eratosthène ou Atkin). Par conséquent, le rapprochement de n th l'idéal serait de ne jamais sous-estimer la valeur réelle de l' n e premier.

(Mise à jour: voir ma réponse pour une bonne méthode de recherche de la limite supérieure de la n ème nombre premier.)

source d'informationauteur David Johnstone

11

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);
}
```
Ces ne devrait jamais être inférieure à la nth_prime, doivent travailler pour un 64-bits d'entrée, et d'un ordre de grandeur ou plus près de la formule de Robin donné plus tôt (ou Wimblik est compliqué gamme limitée de la formule). Pour mon utilisation, j'ai un peu plus petits nombres premiers de la table, donc peut serrer la dernière estimation un peu plus. Techniquement, à partir de formules que nous pourrions utiliser étage() à la place de l'ceil() mais je m'inquiète au sujet de la précision.

Edit: une Autre option pour améliorer un peu tout ça est mise en œuvre des bonnes du premier comte de limites (par exemple, Axler 2014) et en faisant une recherche binaire sur eux. Mon code pour que cette méthode prend ~10x plus que le dessus (toujours en cours d'exécution en vertu d'un ordre de la milliseconde), mais peut réduire le pourcentage d'erreur par un ordre de grandeur.

Si vous souhaitez un devis pour le n-ième nombre premier, vous pouvez le faire:
- Cipolla 1902 (voir Dusart 1999 page 12 ou ce document. Je trouve trois termes (m=2) plus un troisième facteur de correction pour être utile, mais avec plus de termes il oscille trop. La formule indiquée dans le lien Wikipédia est cette formule (avec m=2). À l'aide de la deux mandats inverse li ou à l'inverse de Riemann R ci-dessous donnent de meilleurs résultats.
- Calculer la Dusart 2010 limites supérieures et inférieures et la moyenne des résultats. Pas trop mal, bien que je soupçonne à l'aide d'une moyenne pondérée pourra mieux travailler que les limites ne sont pas aussi serré.
- li^{ -1}(n) Depuis li(n) agit d'une bonne approximation du premier décompte, l'inverse est un décent nth_prime rapprochement. Cela, et tout le reste, peut être fait assez rapidement comme un binaire de recherche sur la fonction.
- li^{ -1}(n) + li^{ -1}(sqrt(n))/4 de plus près, puisque c'est de se rapprocher de R(n)
- R^{ -1} L'inverse de Riemann de la fonction R est le plus proche de la moyenne rapprochement je sais que c'est raisonnable.
Enfin, si vous avez une très rapide, le premier comte de la méthode comme celle de l'AMT implémentations (il y a trois implémentations open source), vous pouvez écrire un rapide précis nth_prime méthode. Le calcul de la 10^10, le premier peut être fait en quelques millisecondes, et le 10^13 en quelques secondes (sur un ordinateur rapide). Les approximations sont extrêmement rapides à toutes les tailles et de travail de plus en plus nombreux, mais tout le monde a une idée différente de ce "grand" signifie.
8

Merci pour toutes ces réponses. Je soupçonne qu'il y a quelque chose d'assez simple comme ça, mais je ne pouvais pas le trouver à l'époque. J'ai fait des recherches un peu plus aussi.

Comme je le veux pour un tamis pour générer le premier n nombres premiers, je veux le rapprochement être supérieure ou égale à la ne premier. (Donc, je veux que la limite supérieure de la nème nombre premier.)

Wikipedia donne l'inī egalitī pour n >= 6
```
p_n <= n log n + n log log n   (1)
```
où p_n est le ne premier, et log est le logarithme naturel. C'est un bon début, mais il peut surestimer par une quantité non négligeable. Cet article dans Le Journal De Mathématiques De Niveau Collégial donne un resserrement de la limite supérieure pour les n >= 7022
```
p_n <= n log n + n (log log n - 0.9385)   (2)
```
C'est beaucoup plus serré lié 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 mis en place mon ne premier approximation de la fonction pour utiliser la seconde approximation pour n >= 7022la première approximation pour 6 <= n < 7022et un tableau de recherche pour les 5 premiers nombres premiers.

(Bien que la première méthode n'est pas très étroitement liés, en particulier pour la plage où je l'utilise, je ne suis pas concerné car je veux ça pour un tamis, et d'un tamis de plus petits nombres est le calcul à bas prix.)
4

Théorème des nombres premiers donne un certain nombre de nombres premiers en dessous d'un seuil de valeur, de sorte qu'il pourrait être utilisé pour donner une valeur approximative pour le n-ième nombre premier.
4

Comme une estimation approximative, vous pouvez utiliser n*ln(n) comme une approximation pour le n-ième nombre premier. Il est beaucoup plus complexe, mais aussi plus précise de la méthode, dont les détails vous pouvez trouver sur Wikipedia ici.

Mon Meilleur Premier(n) Estimation

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 plus récente de la plus expérimentale de la formule.
btw. Les dix billionième premier est 323,780,508,946,331 cette formule fonctionne très bien à cette échelle ne sais pas si il continue de s'approcher à moins 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)))))))

0

Une mise en œuvre efficace est sans doute pas possible avec un tamis. Pensez à ce qui pourrait arriver si vous voulez avoir la première 10.000 nombres premiers. Vous devrez probablement faire un tamis au-dessus d'un énorme plus grande quantité de nombres.

Votre propre implémentation cette question et ma réponse sont de bons moyens à mettre en œuvre sans savoir le rapp. la valeur d'un premier
0

Pour compléter Dana J à la limite Supérieure de cette formule devrait vous donner une bonne borne 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;
```

Vous devez vous connecter pour publier un commentaire.