= Solution
The <Legendre prime-counting formula> counts positive <integers> surviving a finite prime sieve. For $x\geq2$, put $a=\pi(\sqrt{x})$ and let $p_1,\ldots,p_a$ be the <primes> at most $\sqrt{x}$. By <inclusion-exclusion principle>, the number of positive <integers> at most $x$ divisible by none of these <primes> is
$$
\phi(x,a)=\sum_{S\subseteq\{1,\ldots,a\}}(-1)^{|S|}\left\lfloor\frac{x}{\prod_{i\in S}p_i}\right\rfloor.
$$
The empty product is $1$. Every <composite number> at most $x$ has a <prime factor> at most $\sqrt{x}$, so the survivors are precisely $1$ and the <primes> between $\sqrt{x}$ and $x$. Consequently
$$
\boxed{\pi(x)=a-1+\phi(x,a).}
$$
For $x=42$, the sieving <primes> are $2,3,5$, and
$$
\phi(42,3)=42-21-14-8+7+4+2-1=11,\qquad\boxed{\pi(42)=13.}
$$
As a direct check, the <primes> are $2,3,5,7,11,13,17,19,23,29,31,37,41$.
Back to article page
