Legendre's formula

Question

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)?$

Answer 1

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$.

Answer 2

$\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.