Lehmer's Formula

A Formula related to Meissel's Formula.

$$\begin{eqnarray*} \pi(x)&=&\left\lfloor{x}\right\rfloor -\sum_{i=1}^a \left\lfl... ...j=i}^{b_i} \left[{\pi\left({x\over p_ip_j}\right)-(j-1)}\right], \end{eqnarray*}$$

where

$$\begin{eqnarray*} a&\equiv& \pi(x^{1/4})\\ b&\equiv& \pi(x^{1/2})\\ b_i&\equiv& \pi(\sqrt{x/p_i})\\ c&\equiv& \pi(x^{1/3}), \end{eqnarray*}$$

and $\pi(n)$ is the Prime Counting Function.

References

Riesel, H. ``Lehmer's Formula.'' Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 13-14, 1994.