An earlier paper by

*J. C. Lagarias* and

*A. M. Odlyzko* [Lect. Notes Math. 1052, 176-193 (1984;

Zbl 0536.10008)] described two methods for computing

$\pi $ (x), the number of primes

$p\le x$. In the present paper an extended account of the first method is given, with an analysis of its complexity. It is also shown how the use of parallel processing affects the complexity; with M RAM (random access machine) parallel processors, where

$1\le M\le {x}^{1/3}$, at most

$O\left({M}^{-1}{x}^{2/3+\u03f5}\right)$ arithmetic operations are needed and at most

$O\left({x}^{1/3+\u03f5}\right)$ storage locations. Tables of

$\pi $ (x), for various values of x from

${10}^{12}$ to

$4\times {10}^{16}$, are given, showing the discrepancies between

$\pi $ (x), Li(x), and Riemannâ€™s approximation

$R\left(x\right)={\sum}_{n=1}^{\infty}\mu \left(n\right){n}^{-1}Li\left({x}^{1/n}\right)$.