# §27.12 Asymptotic Formulas: Primes

$p_{n}$ is the $n$th prime, beginning with $p_{1}=2$. $\pi\left(x\right)$ is the number of primes less than or equal to $x$.

 27.12.1 $\lim_{n\to\infty}\frac{p_{n}}{n\ln n}=1,$ ⓘ Symbols: $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $p,p_{1},\ldots$: prime numbers Permalink: http://dlmf.nist.gov/27.12.E1 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.12 and Ch.27
 27.12.2 $p_{n}>n\ln n,$ $n=1,2,\dots$. ⓘ Symbols: $\ln\NVar{z}$: principal branch of logarithm function, $n$: positive integer and $p,p_{1},\ldots$: prime numbers Permalink: http://dlmf.nist.gov/27.12.E2 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.12 and Ch.27
 27.12.3 $\pi\left(x\right)=\left\lfloor x\right\rfloor-1-\sum_{p_{j}\leq\sqrt{x}}\left% \lfloor\frac{x}{p_{j}}\right\rfloor+\sum_{r\geq 2}(-1)^{r}\*\sum_{p_{j_{1}} $x\geq 1$,

where the series terminates when the product of the first $r$ primes exceeds $x$.

As $x\to\infty$

 27.12.4 $\pi\left(x\right)\sim\sum_{k=1}^{\infty}\frac{(k-1)!\,x}{(\ln x)^{k}}.$ ⓘ Symbols: $\sim$: Poincaré asymptotic expansion, $!$: factorial (as in $n!$), $\ln\NVar{z}$: principal branch of logarithm function, $\pi\left(\NVar{x}\right)$: number of primes not exceeding a number, $k$: positive integer and $x$: real number Permalink: http://dlmf.nist.gov/27.12.E4 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.12 and Ch.27

## Prime Number Theorem

There exists a positive constant $c$ such that

 27.12.5 $\left|\pi\left(x\right)-\mathrm{li}\left(x\right)\right|=O\left(x\exp\left(-c(% \ln x)^{1/2}\right)\right),$ $x\to\infty$. ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\exp\NVar{z}$: exponential function, $\mathrm{li}\left(\NVar{x}\right)$: logarithmic integral, $\ln\NVar{z}$: principal branch of logarithm function, $\pi\left(\NVar{x}\right)$: number of primes not exceeding a number and $x$: real number Referenced by: Erratum (V1.0.18) for Equation (27.12.5) Permalink: http://dlmf.nist.gov/27.12.E5 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.18): Replaced $\sqrt{\ln x}$ with $(\ln x)^{1/2}$ to be consistent with other equations in this section. Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.12, §27.12 and Ch.27

For the logarithmic integral $\mathrm{li}\left(x\right)$ see (6.2.8). The best available asymptotic error estimate (2009) appears in Korobov (1958) and Vinogradov (1958): there exists a positive constant $d$ such that

 27.12.6 $\left|\pi\left(x\right)-\mathrm{li}\left(x\right)\right|=O\left(x\exp\left(-d(% \ln x)^{3/5}\,(\ln\ln x)^{-1/5}\right)\right).$ ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\exp\NVar{z}$: exponential function, $\mathrm{li}\left(\NVar{x}\right)$: logarithmic integral, $\ln\NVar{z}$: principal branch of logarithm function, $\pi\left(\NVar{x}\right)$: number of primes not exceeding a number, $d$: positive integer and $x$: real number Permalink: http://dlmf.nist.gov/27.12.E6 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.12, §27.12 and Ch.27

$\pi\left(x\right)-\mathrm{li}\left(x\right)$ changes sign infinitely often as $x\to\infty$; see Littlewood (1914), Bays and Hudson (2000).

The Riemann hypothesis25.10(i)) is equivalent to the statement that for every $x\geq 2657$,

 27.12.7 $\left|\pi\left(x\right)-\mathrm{li}\left(x\right)\right|<\frac{1}{8\pi}\sqrt{x% }\,\ln x.$ ⓘ Symbols: $\pi$: the ratio of the circumference of a circle to its diameter, $\mathrm{li}\left(\NVar{x}\right)$: logarithmic integral, $\ln\NVar{z}$: principal branch of logarithm function, $\pi\left(\NVar{x}\right)$: number of primes not exceeding a number and $x$: real number Referenced by: §27.12 Permalink: http://dlmf.nist.gov/27.12.E7 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.12, §27.12 and Ch.27

If $a$ is relatively prime to the modulus $m$, then there are infinitely many primes congruent to $a\pmod{m}$.

The number of such primes not exceeding $x$ is

 27.12.8 $\frac{\mathrm{li}\left(x\right)}{\phi\left(m\right)}+O\left(x\exp\left(-% \lambda(\alpha)(\ln x)^{1/2}\right)\right),$ $m\leq(\ln x)^{\alpha}$, $\alpha>0$, ⓘ Symbols: $O\left(\NVar{x}\right)$: order not exceeding, $\phi\left(\NVar{n}\right)$: Euler’s totient, $\exp\NVar{z}$: exponential function, $\mathrm{li}\left(\NVar{x}\right)$: logarithmic integral, $\ln\NVar{z}$: principal branch of logarithm function, $m$: positive integer and $x$: real number Referenced by: Erratum (V1.0.17) for Equation (27.12.8) Permalink: http://dlmf.nist.gov/27.12.E8 Encodings: TeX, pMML, png Errata (effective with 1.0.17): Originally the first term was given incorrectly by $\frac{x}{\phi\left(m\right)}$. Reported 2017-12-04 by Gergő Nemes Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\ln$ from $\mathrm{log}$. See also: Annotations for §27.12, §27.12 and Ch.27

where $\lambda(\alpha)$ depends only on $\alpha$, and $\phi\left(m\right)$ is the Euler totient function (§27.2).

A Mersenne prime is a prime of the form $2^{p}-1$. The largest known prime (2018) is the Mersenne prime $2^{82,589,933}-1$. For current records see The Great Internet Mersenne Prime Search.

A pseudoprime test is a test that correctly identifies most composite numbers. For example, if $2^{n}\not\equiv 2\pmod{n}$, then $n$ is composite. Descriptions and comparisons of pseudoprime tests are given in Bressoud and Wagon (2000, §§2.4, 4.2, and 8.2) and Crandall and Pomerance (2005, §§3.4–3.6).

A Carmichael number is a composite number $n$ for which $b^{n}\equiv b\pmod{n}$ for all $b\in\mathbb{N}$. There are infinitely many Carmichael numbers.