info prev up next book cdrom email home

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.




© 1996-9 Eric W. Weisstein
1999-05-26