note[5]

例：化简该复杂度

$$\sum_{k=1}^{\pi(n)} \frac{1}{p_k}$$

其中 $\pi(n)$ 为素数计数函数，$p_k$ 表示第 $k$ 大的素数。

来源于 Eratosthenes 筛法 复杂度分析

解：

引理：有以下等式 link

$$\int \frac{\mathrm{d}x}{x \ln x} = \ln(\ln x)$$

证明：

根据换元法公式：令 $u=g(x)$ ，则 $du = g^{\prime}(x)dx$ 。

令 $u = \ln x$ ，则 $\mathrm{d}u = \frac{1}{x}\mathrm{d}x$

$$\int \frac{1}{x \ln x} \mathrm{d}x = \int \frac{1}{u} \mathrm{d}u = \ln u$$

故

$$\int \frac{\mathrm{d}x}{x \ln x} = \ln (\ln x)\qquad$$

证毕。 $\square$

根据素数定理有 $\pi(n) = \Theta\left(\frac{n}{\ln n}\right)$ ，可知第 $n$ 个素数的大小为 $\Theta\left(n\ln n\right)$

则有

$$\begin{aligned} \sum_{k=1}^{\pi(n)} \frac{1}{p_k} &= \mathcal{O}\left(\sum_{k=2}^{\pi(n)} \frac{1}{k \ln k}\right) \\&=\mathcal{O}\left(\int_2^{\pi(n)} \frac{\mathrm{d}x}{x \ln x}\right) \end{aligned}$$

根据引理可得

$$\mathcal{O}\left(\int_2^{\pi(n)} \frac{\mathrm{d}x}{x \ln x}\right) = \mathcal{O}\left(\ln \ln \pi(n)\right) = \mathcal{O}\left(\log \log n\right)$$

---

参考文献

[1] https://www.sudoedu.com/%e9%ab%98%e7%ad%89%e6%95%b0%e5%ad%a6%ef%bc%88%e4%b8%8a%ef%bc%89%e8%a7%86%e9%a2%91%e8%af%be%e7%a8%8b/%e4%b8%8d%e5%ae%9a%e7%a7%af%e5%88%86/%e7%ac%ac%e4%b8%80%e7%b1%bb%e6%8d%a2%e5%85%83%e6%b3%95/