# §27.12 Asymptotic Formulas: Primes

$p_{n}$ is the $n$th prime, beginning with $p_{1}=2$. $\mathop{\pi\/}\nolimits\!\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\mathop{\ln\/}\nolimits n}=1,$ Symbols: $\mathop{\ln\/}\nolimits\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 $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: Annotations for 27.12
 27.12.2 $p_{n}>n\mathop{\ln\/}\nolimits n,$ $n=1,2,\dots$. Symbols: $\mathop{\ln\/}\nolimits\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 $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: Annotations for 27.12
 27.12.3 $\mathop{\pi\/}\nolimits\!\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 $\mathop{\pi\/}\nolimits\!\left(x\right)\sim\sum_{k=1}^{\infty}\frac{(k-1)!\,x}% {(\mathop{\ln\/}\nolimits x)^{k}}.$ Symbols: $\sim$: Poincaré asymptotic expansion, $!$: factorial (as in $n!$), $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $\mathop{\pi\/}\nolimits\!\left(\NVar{x}\right)$: number of primes not exceeding $x$, $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 $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: Annotations for 27.12

## Prime Number Theorem

There exists a positive constant $c$ such that

 27.12.5 $\left|\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits% \!\left(x\right)\right|=\mathop{O\/}\nolimits\!\left(x\mathop{\exp\/}\nolimits% \left(-c\sqrt{\mathop{\ln\/}\nolimits x}\right)\right),$ $x\to\infty$. Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\exp\/}\nolimits\NVar{z}$: exponential function, $\mathop{\mathrm{li}\/}\nolimits\!\left(\NVar{x}\right)$: logarithmic integral, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $\mathop{\pi\/}\nolimits\!\left(\NVar{x}\right)$: number of primes not exceeding $x$ and $x$: real number Permalink: http://dlmf.nist.gov/27.12.E5 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: Annotations for 27.12

For the logarithmic integral $\mathop{\mathrm{li}\/}\nolimits\!\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|\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits% \!\left(x\right)\right|=\mathop{O\/}\nolimits\!\left(x\mathop{\exp\/}\nolimits% \!\left(-d(\mathop{\ln\/}\nolimits x)^{3/5}\,(\mathop{\ln\/}\nolimits\mathop{% \ln\/}\nolimits x)^{-1/5}\right)\right).$ Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\exp\/}\nolimits\NVar{z}$: exponential function, $\mathop{\mathrm{li}\/}\nolimits\!\left(\NVar{x}\right)$: logarithmic integral, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $\mathop{\pi\/}\nolimits\!\left(\NVar{x}\right)$: number of primes not exceeding $x$, $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 $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: Annotations for 27.12

$\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits\!\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|\mathop{\pi\/}\nolimits\!\left(x\right)-\mathop{\mathrm{li}\/}\nolimits% \!\left(x\right)\right|<\frac{1}{8\pi}\sqrt{x}\,\mathop{\ln\/}\nolimits x.$ Symbols: $\pi$: the ratio of the circumference of a circle to its diameter, $\mathop{\mathrm{li}\/}\nolimits\!\left(\NVar{x}\right)$: logarithmic integral, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $\mathop{\pi\/}\nolimits\!\left(\NVar{x}\right)$: number of primes not exceeding $x$ 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 $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: Annotations for 27.12

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{x}{\mathop{\phi\/}\nolimits\!\left(m\right)}+\mathop{O\/}\nolimits\!% \left(x\mathop{\exp\/}\nolimits\!\left(-\lambda(\alpha)(\mathop{\ln\/}% \nolimits x)^{1/2}\right)\right),$ $m\leq(\mathop{\ln\/}\nolimits x)^{\alpha}$, $\alpha>0$, Symbols: $\mathop{O\/}\nolimits\!\left(\NVar{x}\right)$: order not exceeding, $\mathop{\phi\/}\nolimits\!\left(\NVar{n}\right)$: Euler’s totient, $\mathop{\exp\/}\nolimits\NVar{z}$: exponential function, $\mathop{\ln\/}\nolimits\NVar{z}$: principal branch of logarithm function, $m$: positive integer and $x$: real number Permalink: http://dlmf.nist.gov/27.12.E8 Encodings: TeX, pMML, png Change of Notation (effective with 1.0.10): The notation for logarithm has been changed to $\mathop{\ln\/}\nolimits$ from $\mathrm{log}$. Reported 2015-06-08 See also: Annotations for 27.12

where $\lambda(\alpha)$ depends only on $\alpha$, and $\mathop{\phi\/}\nolimits\!\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 (2009) is the Mersenne prime $2^{43,112,609}-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.