Elementary proof on analysis of Eratosthenes' Sieve

篩法複雜度

直觀的篩法複雜度為 $\Theta(n\log\log n)$ 次數值計算（我們假設乘法、加法都是常數時間）。 我們要證明的便是 Mertens’ Theorem 的弱化版。

下界的證明

$$\begin{align*} \sum_{k\le n} \frac{1}{k} & \le \prod_{p\le n}\left(1 + \frac{1}{p}\right)\sum \frac{1}{k^2}\\ & \le \prod_{p\le n} e^{1/p} \sum \frac{1}{k^2}\\ & \le \frac{\pi^2}{6} \prod_{p\le n} e^{1/p}\\ & \le \frac{\pi^2}{6} \exp\left( \sum_{p \le n} \frac{1}{p}\right) \end{align*}$$

所以，得出：

$$\begin{align*} \sum_{p\le n} \frac{1}{p} & \ge \ln\left(\frac{6}{\pi^2} \sum_{k\le n} \frac{1}{k}\right)\\ & = \ln\ln n + O(1) \end{align*}$$

上界的證明

$$\begin{align*} \sum_{p\le n}\frac{1}{p} &\le \sum_{p\le n} \frac{1}{p}\frac{\ln p}{\ln p} \\ &< \sum_{p\le n}\frac{1}{p\ln p}\left(2+\frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{p}\right)\\ &= \sum_{p\le n} \left(\frac{2}{p\ln p} + \frac{1}{2p\ln p} + \frac{1}{3p\ln p} + \cdots + \frac{1}{p^2\ln p}\right)\\ &= \sum_{p\le n} \left(\frac{2}{p\ln p} + \frac{2}{2p\ln p^2} + \frac{2}{3p\ln p^2} + \cdots + \frac{2}{p^2\ln p^2}\right)\\ &< 2\sum_{p\le n} \left(\frac{1}{p\ln p} + \frac{1}{2p\ln(2p)} + \frac{1}{3p\ln(3p)} + \cdots + \frac{1}{p^2\ln p^2}\right)\\ &\le 2\sum_{k\le n^2} \frac{1}{k\ln k} \\ &\le 2\ln\ln n + O(1) \end{align*}$$