[proofplan] We use finite inclusion-exclusion over the prime numbers at most $y$ to count the integers $n \leq x$ with no prime divisor at most $y$. The Möbius function sum over divisors of $P(y+1)$ is exactly the indicator of having greatest common divisor equal to $1$ with $P(y+1)$. Since every composite integer $2 \leq n \leq x$ has a prime divisor at most $\sqrt{x}$, the integers surviving the sieve are precisely $1$ together with the primes $p$ satisfying $y < p \leq x$. Rearranging this count gives the stated formula for the prime-counting function $\pi$. [/proofplan] [step:Convert the Möbius divisor sum into a coprimality indicator] Define the finite set \begin{align*} A_x := \{n \in \mathbb{N} : 1 \leq n \leq \lfloor x \rfloor\}. \end{align*} Define \begin{align*} P := P(y+1) = \prod_{p \leq y,\ p \text{ prime}} p. \end{align*} For each $n \in A_x$, let $\gcd(n,P)$ denote the greatest common divisor of the two positive integers $n$ and $P$. We claim that the following two alternatives hold. If $\gcd(n,P)=1$, then \begin{align*} \sum_{d \mid P,\ d \mid n} \mu(d) = 1. \end{align*} If $\gcd(n,P)>1$, then \begin{align*} \sum_{d \mid P,\ d \mid n} \mu(d) = 0. \end{align*} Indeed, because $P$ is squarefree, every divisor $d \mid P$ is a product of a subset of the primes dividing $P$. Let \begin{align*} S_n := \{p : p \text{ is prime},\ p \mid P,\ p \mid n\}. \end{align*} Then the divisors $d \mid P$ with $d \mid n$ are exactly the products of subsets of $S_n$. By the defining formula for the Möbius function on squarefree integers, $\mu(d)=(-1)^k$ when $d$ is a product of $k$ distinct primes. Hence \begin{align*} \sum_{d \mid P,\ d \mid n} \mu(d) = \sum_{T \subseteq S_n} (-1)^{|T|} = (1 - 1)^{|S_n|}. \end{align*} This equals $1$ when $S_n = \varnothing$, equivalently $\gcd(n,P)=1$, and equals $0$ otherwise. [guided] The purpose of the Möbius sum is to build an exact indicator function for the condition that $n$ has no prime factor at most $y$. We define \begin{align*} P := P(y+1) = \prod_{p \leq y,\ p \text{ prime}} p. \end{align*} Thus the prime divisors of $P$ are precisely the primes at most $y$. Fix $n \in A_x$, where \begin{align*} A_x := \{n \in \mathbb{N} : 1 \leq n \leq \lfloor x \rfloor\}. \end{align*} Let $\gcd(n,P)$ denote the greatest common divisor of the two positive integers $n$ and $P$. We examine \begin{align*} \sum_{d \mid P,\ d \mid n} \mu(d). \end{align*} Here $\mu$ denotes the Möbius function. Since $P$ is squarefree, each divisor $d \mid P$ is obtained by choosing a subset of the prime divisors of $P$ and multiplying those primes. Let \begin{align*} S_n := \{p : p \text{ is prime},\ p \mid P,\ p \mid n\}. \end{align*} Then the divisors $d \mid P$ that also divide $n$ are exactly the products of subsets of $S_n$. If $T \subseteq S_n$, the corresponding divisor has $|T|$ distinct prime factors, so its Möbius value is $(-1)^{|T|}$. Therefore \begin{align*} \sum_{d \mid P,\ d \mid n} \mu(d) = \sum_{T \subseteq S_n} (-1)^{|T|} = (1 - 1)^{|S_n|}. \end{align*} If $S_n$ is empty, then no prime divisor of $P$ divides $n$, so $\gcd(n,P)=1$, and the sum is $1$. If $S_n$ is nonempty, then $n$ shares at least one prime factor with $P$, so $\gcd(n,P)>1$, and the sum is $0$. Hence the Möbius sum is exactly the indicator of the condition $\gcd(n,P)=1$. [/guided] [/step] [step:Sum the indicator over the interval and interchange the finite sums] Summing the identity from the previous step over $n \in A_x$ gives \begin{align*} |\{n \in A_x : \gcd(n,P)=1\}| = \sum_{n \in A_x} \sum_{d \mid P,\ d \mid n} \mu(d). \end{align*} All sums are finite, so we may interchange the order of summation: \begin{align*} |\{n \in A_x : \gcd(n,P)=1\}| = \sum_{d \mid P} \mu(d)\, |\{n \in A_x : d \mid n\}|. \end{align*} For each positive divisor $d \mid P$, the integers $n \in A_x$ divisible by $d$ are exactly $d,2d,\dots,\lfloor x/d \rfloor d$, so \begin{align*} |\{n \in A_x : d \mid n\}| = \left\lfloor \frac{x}{d} \right\rfloor. \end{align*} Therefore \begin{align*} |\{n \in A_x : \gcd(n,P)=1\}| = \sum_{d \mid P} \mu(d) \left\lfloor \frac{x}{d} \right\rfloor. \end{align*} [/step] [step:Identify the integers that survive the sieve] We claim that \begin{align*} \{n \in A_x : \gcd(n,P)=1\} = \{1\} \cup \{p : p \text{ is prime and } y < p \leq x\}. \end{align*} First, $1$ is coprime to $P$. If $p$ is prime and $y < p \leq x$, then no prime divisor of $P$ equals $p$, and the only positive prime divisor of $p$ is $p$ itself; hence $\gcd(p,P)=1$. Conversely, let $n \in A_x$ with $n \geq 2$ and $\gcd(n,P)=1$. If $n$ were composite, then $n = ab$ for integers $a,b$ with $2 \leq a \leq b$. Thus $a^2 \leq n \leq x$, so $a \leq \sqrt{x}$. Let $q$ be a prime divisor of $a$. Then \begin{align*} q \leq a \leq \sqrt{x}. \end{align*} Since $y=\lfloor \sqrt{x}\rfloor$ and $q$ is an integer, this implies $q \leq y$. Hence $q \mid P$. Also $q \mid a$ and $a \mid n$, so $q \mid n$, contradicting $\gcd(n,P)=1$. Therefore $n$ is prime. Since $\gcd(n,P)=1$, this prime cannot satisfy $n \leq y$, so $y < n \leq x$. [/step] [step:Rearrange the survivor count to obtain Legendre's formula] From the previous step, \begin{align*} |\{n \in A_x : \gcd(n,P)=1\}| = 1 + |\{p : p \text{ is prime and } y < p \leq x\}|. \end{align*} By the definition of the prime-counting function, the number of primes $p$ with $y < p \leq x$ is $\pi(x)-\pi(y)$, so \begin{align*} |\{n \in A_x : \gcd(n,P)=1\}| = 1 + \pi(x) - \pi(y). \end{align*} Combining this with the sieve count gives \begin{align*} 1 + \pi(x) - \pi(y) = \sum_{d \mid P(y+1)} \mu(d) \left\lfloor \frac{x}{d} \right\rfloor. \end{align*} Rearranging, \begin{align*} \pi(x) = \pi(y) - 1 + \sum_{d \mid P(y+1)} \mu(d) \left\lfloor \frac{x}{d} \right\rfloor. \end{align*} This is the desired formula. [/step]