An overview of methods for precise counting of the number of primes not
exceeding an arbitrary integer 
is given in Crandall and Pomerance (2005, §3.7).
T. Oliveira e Silva has calculated 
for 
,
using the combinatorial methods of Lagarias et al. (1985) and
Deléglise and Rivat (1996); see Oliveira e Silva (2006). An analytic approach using a contour integral of the Riemann zeta function
(§25.2(i)) is discussed in Borwein et al. (2000).
The Sieve of Eratosthenes (Crandall and Pomerance (2005, §3.2)) generates a list of all primes below a given bound. An alternative procedure is the binary quadratic sieve of Atkin and Bernstein (Crandall and Pomerance (2005, p. 170)).
For small values of 
, primality is proven by showing that is not
divisible by any prime not exceeding 
.
Two simple algorithms for proving primality require a knowledge of all or part
of the factorization of 
, or both; see
Crandall and Pomerance (2005, §§4.1–4.2). These algorithms are used for testing
primality of Mersenne numbers, 
, and Fermat numbers,
.
The APR (Adleman–Pomerance–Rumely) algorithm for primality testing
is based on Jacobi sums. It runs in time 
.
Explanations are given in Cohen (1993, §9.1) and
Crandall and Pomerance (2005, §4.4). A practical version is described in
Bosma and van der Hulst (1990).
The AKS (Agrawal–Kayal–Saxena) algorithm is the first deterministic,
polynomial-time, primality test. That is to say, it runs in time
for some constant 
. An explanation is given in
Crandall and Pomerance (2005, §4.5).
