# Legendre's formula

Legendre's formula counts the number of positive integers less than or equal to a number $x$ which are not divisible by any of the first $a$ primes: \begin{align} &\phi(x,a)=\lfloor x \rfloor-\sum_{p_i\le a}\left\lfloor \dfrac{ x }{(p_i)}\right\rfloor+\sum_{p_i<p_j\le a}\left\lfloor\dfrac{ x}{(p_ip_j)}\right\rfloor-\sum_{p_i<p_j<p_k\le a}\left\lfloor \dfrac{x}{(p_ip_jp_k)}\right\rfloor+\dots \end{align} then $\pi(x)=\phi\bigl(x,\pi (\sqrt{x})\bigr)+\pi (\sqrt{x})-1$ as given here.

My question is, why does $\bigl\lfloor\phi(x,\lfloor\sqrt{x}\rfloor)+\sqrt{x}-1\bigr\rfloor$ also equal $\pi(x)?$

• I don't have time to think about this carefully, hence a comment, not an answer: Any number $\le x$ which is not divisible by any prime $\le\sqrt{x}$ is a prime number. So roughly speaking, $\phi\bigl(x,\lfloor\sqrt{x}\rfloor\bigr)$ counts the primes $\le x$. However, it misses the primes $\le \sqrt{x}$, which are after all divisible by themselves. So those have to be added back. It only remains to clear up any off-by-one errors, I think … – Harald Hanche-Olsen Aug 31 '14 at 15:43

Note: In your sums, you must have $i\leqslant a$ etc. instead of $p_i \leqslant a$ to consider the first $a$ primes, and not the primes $\leqslant a$.
Whenever $a \geqslant \pi(\sqrt{x})$, the numbers $\leqslant x$ not divisible by any of the first $a$ primes are the primes between $p_a$ (exclusive) and $x$ (inclusive), and $1$. So then you have
$$\phi(x,a) = \pi(x) - a + 1.$$
Since $\lfloor \sqrt{x}\rfloor \geqslant \pi(\sqrt{x})$, the identity follows for $a = \lfloor\sqrt{x}\rfloor$.
$\phi(x,\pi(\sqrt{x}))$ is the number of positive integers $\le x$ which are not divisible by any prime $\le\sqrt{x}$. In other words, it is a count of the primes which are $\le x$ but $>\sqrt{x}$. Except that it also counts 1 (which is not considered a prime. So to get $\pi(x)$ we need to add the number of primes $\le\sqrt{x}$ which is just $\pi(\sqrt{x})$ and subtract 1.