Meissel's Formula

A modification of Legendre's Formula for the Prime Counting Function $\pi(x)$ . It starts with

$\displaystyle \left\lfloor{x}\right\rfloor$	$\textstyle =$	$\displaystyle 1+\sum_{1\leq i\leq a} \left\lfloor{x\over p_i}\right\rfloor -\su... ...\sum_{1\leq i < j < k\leq a}\left\lfloor{x\over p_ip_jp_k}\right\rfloor -\ldots$
	$\textstyle \phantom{=}$	$\displaystyle \mathop{+}\pi(x)-a+P_2(x,a)+P_3(x,a)+\ldots,$	(1)

where $\left\lfloor{x}\right\rfloor$ is the Floor Function,

is the number of Integers $p_ip_j\leq x$ with $a+1\leq j\leq j$ , and

is the number of Integers $p_ip_jp_k\leq x$ with $a+1\leq i\leq j\leq k$ . Identities satisfied by the

s include

$\begin{displaymath} P_2(x,a) = \sum\left[{\pi\left({x\over p_i}\right)-(i-1)}\right] \end{displaymath}$

(2)

for $p_a<p_i\leq \sqrt{x}$ and

$\displaystyle P_3(x,a)$	$\textstyle =$	$\displaystyle \sum_{i>a} P_2\left({{x\over p_i} , a}\right)$
	$\textstyle =$	$\displaystyle \sum_{i=a+1}^c \sum_{j=i}^{\pi(\sqrt{x/p_i})}\left[{\pi\left({x\over p_ip_j}\right)-(j-1)}\right].$	(3)

Meissel's formula is

$\displaystyle \pi(x)$	$\textstyle =$	$\displaystyle \left\lfloor{x}\right\rfloor -\sum_{i=1}^c \left\lfloor{x\over p_... ...oor +\sum_{1\leq i\leq j\leq c}\left\lfloor{x\over p_ip_j}\right\rfloor -\ldots$
	$\textstyle \phantom{=}$	$\displaystyle +{\textstyle{1\over 2}}(b+c-2)(b-c+1)-\sum_{c\leq i\leq b} \pi\left({x\over p_i}\right),$	(4)

where

$\displaystyle b$	$\textstyle \equiv$	$\displaystyle \pi(x^{1/2})$	(5)
$\displaystyle c$	$\textstyle \equiv$	$\displaystyle \pi(x^{1/3}).$	(6)

Taking the derivation one step further yields Lehmer's Formula.

References

Riesel, H. ``Meissel's Formula.'' Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, p. 12, 1994.