Computing π(x): the combinatorial method

Abstract

This article presents a self-contained description of the method proposed by Deléglise and Rivat — which has roots on earlier work by Meissel, by Lehmer, and by Lagarias, Miller and Odlyzko—to compute π(x), which is the number of primes not larger than x. To make life easier to programmers, the major parts of the computation of π(x) are also presented in algorithmic form. The more interesting low-level computational details are presented in the form of of C code snippets.