[proofplan] We use unique factorisation to write every integer $n \leq x$ in the form $n = k^2 m$ where $m$ is square-free. The square-free part $m$ is a product of distinct primes $\leq x$, so there are at most $2^{\pi(x)}$ possibilities for $m$. The square part $k^2$ satisfies $k \leq \sqrt{x}$, giving at most $\sqrt{x}$ possibilities for $k$. Combining these two counts bounds $x$ above by $\sqrt{x} \cdot 2^{\pi(x)}$, and solving for $\pi(x)$ gives the logarithmic lower bound. [/proofplan] [step:Enumerate the primes up to $x$ and parametrise each $n \leq x$ by a square $\times$ square-free decomposition] Fix an integer $x \geq 1$. Let $r = \pi(x)$, and enumerate the primes up to $x$ as $p_1 < p_2 < \cdots < p_r$ (if $x = 1$ then $r = 0$ and the set of primes is empty; the argument below still applies vacuously). Every positive integer $n$ has a unique factorisation $n = k^2 m$ with $k \in \mathbb{N}$ and $m$ square-free. This is proved by collecting the prime factors of $n$ into those appearing to even exponent (which contribute to $k^2$) and those appearing to odd exponent (which contribute to $m$, each with exponent $1$ after removing a square): explicitly, if $n = \prod_i q_i^{e_i}$ is the prime factorisation, set $k = \prod_i q_i^{\lfloor e_i / 2 \rfloor}$ and $m = \prod_{i : e_i \text{ odd}} q_i$. Uniqueness follows from uniqueness of prime factorisation. If $n \leq x$ and $n = k^2 m$ with $m$ square-free, then in particular every prime factor of $n$ — and hence every prime factor of $m$ — divides $n$ and is therefore $\leq n \leq x$. Thus the prime factors of $m$ all lie in $\{p_1, \ldots, p_r\}$, and $m$ is a product of a subset of these primes (each appearing to the first power since $m$ is square-free). Moreover $k^2 \leq k^2 m = n \leq x$, so $k \leq \sqrt{x}$. [/step] [step:Count the number of choices for the square part and the square-free part] Define the map \begin{align*} \Phi: \{n \in \mathbb{N} : n \leq x\} &\to \{k \in \mathbb{N} : 1 \leq k \leq \sqrt{x}\} \times \{0, 1\}^r \\ n &\mapsto (k, (\alpha_1, \ldots, \alpha_r)) \end{align*} where $n = k^2 m$ with $m = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$ and $\alpha_i \in \{0, 1\}$. The map $\Phi$ is well-defined by Step 1 (the decomposition exists and is unique, $k \leq \sqrt{x}$, and the prime factors of $m$ are among $p_1, \ldots, p_r$) and injective because $n = k^2 m$ is recovered uniquely from $(k, (\alpha_i))$. Since $\Phi$ is injective, the cardinality of its domain is bounded by that of its codomain. The domain has cardinality $\lfloor x \rfloor$, and the codomain has cardinality \begin{align*} |\{k \in \mathbb{N} : 1 \leq k \leq \sqrt{x}\}| \cdot |\{0, 1\}^r| = \lfloor \sqrt{x} \rfloor \cdot 2^r \leq \sqrt{x} \cdot 2^r. \end{align*} Hence, using $x \leq \lfloor x \rfloor + 1$ would introduce a minor correction; instead we observe that $x \geq 1$ and the domain has at least $\lfloor x \rfloor$ elements, which we relate to $x$ directly by noting the slightly sharper statement — we use $\lfloor x \rfloor \geq x/2$ for $x \geq 1$ if needed, but for integer $x$ the domain has exactly $x$ elements and \begin{align*} x \leq \sqrt{x} \cdot 2^r. \end{align*} [/step] [step:Solve the inequality for $\pi(x)$] From $x \leq \sqrt{x} \cdot 2^r$ with $r = \pi(x)$, dividing both sides by $\sqrt{x} > 0$ (valid for $x \geq 1$) gives \begin{align*} \sqrt{x} \leq 2^{\pi(x)}. \end{align*} Taking the natural logarithm of both sides — a strictly increasing function — preserves the inequality: \begin{align*} \frac{1}{2} \log x \leq \pi(x) \log 2. \end{align*} Dividing by $\log 2 > 0$ yields the claimed bound \begin{align*} \pi(x) \geq \frac{\log x}{2 \log 2}. \end{align*} This completes the proof. We remark that the bound is vacuous for $x = 1$ (where $\log 1 = 0$ and $\pi(1) = 0$), and in fact equality holds only in degenerate cases; the bound grows logarithmically and is therefore much weaker than the [Prime Number Theorem](/theorems/1742), but it suffices to show that $\pi(x) \to \infty$ and hence that there are infinitely many primes. [/step]