Fonction de Comptage des Premiers

La fonction de comptage des nombres premiers, appelée $ \pi(n) $, a pour but de dénombrer/compter les nombres premiers inférieurs ou égaux à un nombre $ n $

Pour les petits nombres, la méthode la plus directe pour compter rapidement tous les premiers inférieurs à $ n $ est d'utiliser la crible d'Ératosthène afin de lister les nombres premiers.

La valeur de pi(n) tend vers $ n / \ln(n) $ lorsque $ n $ tend vers l'infini (c'est à dire que $ n / \ln(n) $ est une bonne approximation de $ pi(n) $ lorsque $ n $ est très grand)

$$ \pi(n)\ \underset{ n \to \infty }{ \sim } \frac{n}{\ln(n)} $$

Cette formule est aussi appelée le théorème des nombres premiers.

Le calcul de pi(n) permet de positionner un nombre premier par rapport à un autre, en connaissant son rang dans la liste des nombres premiers.

Si $ \pi(a) < \pi(b) $ alors $ a < b $.

Une conséquence du théorème des nombres premiers est que le nième nombre premier $ p_n $ est proche de $ n \ln(n) $ (et d'avantage lorsque $ n $ est très grand) $$ p_n \underset{ n \to \infty }{ \sim } n \ln (n) $$