Sieve methods

This equivalence is exactly what lets the sieve stop early: once every prime up to $\sqrt N$ has crossed off its multiples, there is no possible witness left to convict any remaining number of being composite, so testing (or crossing off) larger primes is provably wasted work.

($\Leftarrow$) Suppose $n$ has no prime factor $\le\sqrt n$. If $n$ were composite, write $n=ab$ with $1<a\le b<n$. Then $a\le\sqrt n$ (otherwise $a>\sqrt n$ and $b\ge a>\sqrt n$ would force $ab>n$, a contradiction), and $a$'s smallest prime factor $p$ satisfies $p\le a\le\sqrt n$, so $p$ is a prime factor of $n$ that is $\le\sqrt n$ — contradicting the hypothesis. So $n$ has no such factorization, hence $n$ is prime.

($\Rightarrow$) If $n$ is prime, its only positive divisors are $1$ and $n$; no prime $p<n$ divides it at all, so in particular none with $p\le\sqrt n$ does either.

Together these show the two conditions are equivalent, which is exactly the termination criterion used in the sieve: after processing every prime up to $\sqrt N$, everything still unmarked in $[2,N]$ satisfies the right-hand side, hence is prime.

This is the precise, quantitative version of "cross off multiples": instead of physically marking a grid, it counts survivors directly by inclusion–exclusion over which small primes divide them. It is the ancestor of every modern sieve (Brun, Selberg, the large sieve, GPY) used to attack twin primes and bounded gaps — all of them are, at bottom, smarter ways of controlling the error terms that this exact formula produces.

Every integer $a\in A$ is coprime to $P(z)$ iff it is divisible by none of the primes $p<z$. For each divisor $d\mid P(z)$ (a squarefree product of some subset of these primes), the count of multiples of $d$ in $A=\{1,\ldots,x\}$ is exactly $\lfloor x/d\rfloor$.

By inclusion–exclusion over the events "$p\mid a$" for $p<z$: the count of $a\in A$ divisible by at least one prime in $\mathcal P$ is $\sum_{p<z}\lfloor x/p\rfloor - \sum_{p<q}\lfloor x/(pq)\rfloor + \sum_{p<q<r}\lfloor x/(pqr)\rfloor - \cdots$, alternating with the number of primes multiplied together. Each such alternating sign is exactly the Möbius function $\mu(d)$ of the corresponding squarefree $d\mid P(z)$: $\mu(1)=1$, $\mu(d)=(-1)^k$ for $d$ a product of $k$ distinct primes.

So the count divisible by at least one prime in $\mathcal P$ is $-\sum_{d\mid P(z),\,d>1}\mu(d)\lfloor x/d\rfloor$. Subtracting this from $|A|=\lfloor x\rfloor=x$ (the $d=1$ term, $\mu(1)\lfloor x/1\rfloor=x$) gives the count coprime to $P(z)$: $S(A,\mathcal P,z)=x-\sum_{d\mid P(z),d>1}\mu(d)\lfloor x/d\rfloor=\sum_{d\mid P(z)}\mu(d)\lfloor x/d\rfloor$.

Finally, taking $z=\sqrt x+1$ so that $\mathcal P$ is exactly the primes $\le\sqrt x$: any $a\in[2,x]$ coprime to all of them is either $1$ or a prime $>\sqrt x$ (by the theorem above, since it has no prime factor $\le\sqrt x$), so $S(A,\mathcal P,\sqrt x+1)=1+\big(\pi(x)-\pi(\sqrt x)\big)$, giving the stated identity.