What's New
About the Project
NIST
27 Functions of Number TheoryMultiplicative Number Theory

§27.12 Asymptotic Formulas: Primes

pn is the nth prime, beginning with p1=2. π(x) is the number of primes less than or equal to x.

27.12.1 limnpnnlogn=1,
27.12.2 pn>nlogn,
n=1,2,.
27.12.3 π(x)=x-1-pjxxpj+r2(-1)rpj1<pj2<<pjrxxpj1pj2pjr,
x1,

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

As x

27.12.4 π(x)k=1(k-1)!x(logx)k.

Prime Number Theorem

There exists a positive constant c such that

27.12.5 |π(x)-li(x)|=O(xexp(-clogx)),
x.

For the logarithmic integral li(x) 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 |π(x)-li(x)|=O(xexp(-d(logx)3/5(loglogx)-1/5)).

π(x)-li(x) changes sign infinitely often as x; see Littlewood (1914), Bays and Hudson (2000).

The Riemann hypothesis25.10(i)) is equivalent to the statement that for every x2657,

27.12.7 |π(x)-li(x)|<18πxlogx.

If a is relatively prime to the modulus m, then there are infinitely many primes congruent to a(modm).

The number of such primes not exceeding x is

27.12.8 xϕ(m)+O(xexp(-λ(α)(logx)1/2)),
m(logx)α, α>0,

where λ(α) depends only on α, and ϕ(m) is the Euler totient function (§27.2).

A Mersenne prime is a prime of the form 2p-1. The largest known prime (2009) is the Mersenne prime 243,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 2n2(modn), 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 bnb(modn) for all b. There are infinitely many Carmichael numbers.