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).