Est-il correct d'utiliser une table de valeurs interpolées de la fonction de comptage principal `pi (x)` comme limite supérieure pour un tableau de nombres premiers?

Question

Supposons que je souhaite allouer un tableau d'entiers pour stocker tous les nombres premiers inférieurs à certains N. J'aurais alors besoin d'une estimation pour la taille du tableau, E(N). Il y a une fonction mathématique qui donne le nombre exact de nombres premiers en dessous de N, c'est le Prime-counting function - pi(n). Cependant, il semble impossible de définir la fonction en termes de fonctions élémentaires.

Il existe quelques approximations de la fonction, mais toutes sont des approximations asymptotiques, donc elles peuvent être soit au-dessus ou au-dessous du vrai nombre de nombres premiers et ne peuvent généralement pas être utilisées comme estimation E(N).

J'ai essayé d'utiliser des valeurs tabulées de pi(n) pour certains n comme power-of-two et d'interpoler entre eux. Cependant, j'ai remarqué que la fonction pi(n) est convexe, de sorte que l'interpolation entre les points de la table clairsemée peut donner accidentellement des valeurs de E(n) sous le vrai pi(n) qui peut entraîner un dépassement de tampon.

Je me suis alors décidé d'exploiter la nature et monotones de pi(n) utiliser les valeurs de la table de pi(2^(n+1)) comme une estimation bien supérieure pour E(2^n) un interpoler entre eux cette fois-ci.

Je ne me sens toujours pas complètement certain que pour certains 2^n < X < 2^(n+1) une interpolation entre pi(2^(n+1)) et pi(2^(n+2)) serait l'estimation supérieure sûre. Est-ce correct? Comment puis-je le prouver?

Answer 1

Utilisez une limite supérieure. Il y a un certain nombre à choisir, chacun plus compliqué mais plus serré. J'appelle cela prime_count_upper(n) puisque vous voulez une valeur garantie supérieure ou égale au nombre de nombres premiers sous n. Voir Chebyshev, Rosser et Schoenfeld, Dusart 1999, Dusart 2010, Axler 2014, et Büthe 2015. R & S est simple et pas terrible: π(x) <= x/(log(x)-3/2) for x >= 67 mais Dusart donne de meilleurs pour des valeurs plus grandes. De toute façon, pas de tables ou de recherche originale nécessaire.

Answer 2

Vous êtes en train de trop réfléchir. En C, vous utilisez simplement malloc et realloc. Je préférerais 100 fois un algorithme qui fonctionne évidemment au lieu d'un qui nécessite une preuve mathématique profonde.

Answer 3

Le théorème des nombres premiers garantit la n e premier P (n) est sur la plage n log n < P (n) < n log n + n log log n pour n> 5. Comme le suggère DanaJ, des limites plus étroites peuvent être calculées.

Si vous voulez stocker les nombres premiers dans un tableau, vous ne pouvez pas parler de quelque chose de trop grand. Comme vous le suggérez, il n'y a pas de calcul direct de pi (n) en termes de fonctions arithmétiques élémentaires, mais il y a plusieurs méthodes pour calculer exactement (n n'est pas trop gros. Voir this, par exemple.