有人想求 \(\sum \limits _{i = 2} ^{n} \log (lpf(i))\) 的增長速度，但是被卡了一天.jpg

不過有一個伴生的結論。
若 \(p, q, r\) 均為素數，則 \(<n\) 的形如 \(pqr\) 的數的個數為 \(O(n \frac{\log^2 \log n}{\log n})\)

首先我們容易列一個式子出來。

改寫一下變成

不妨設 \(B = \frac{n}{i}\)，后面的和式寫成 \(\sum \limits_{j \in \mathbb{P}}^{B} \frac{1}{j \log \frac{B}{j}}\)
在后面的處理中，我們可能希望 \(B\) 盡可能的大。
因此我們不妨假設 \(i < \sqrt n\)
這對答案沒有影響。

我們發現目前有兩個不太好處理的東西，一個是 \(j \in \mathbb{P}\)，另一個是 \(\log \frac{n}{ij}\)

不妨按照 \(\sqrt B\) 拆開成兩半。

首先是 \(j < \sqrt B\) 的部分，這里我們知道 \(\log \frac{B}{j}\) 可以直接視為 \(\log B\)

然后就是 \(\frac{1}{\log B} \sum \limits_{j \in \mathbb{P}}^{\sqrt B} \frac{1}{j}\)
二進制分分組就是

然后是 \(j > \sqrt B\) 的部分，這里我們知道素數密度可以近似為 \(\frac{1}{\log B}\)
然后就是 \(\frac{1}{\log B} \sum \limits_{j = \sqrt B}^{B} \frac{1}{j \log \frac{B}{j}}\)
仍然是傳統手藝分組。

綜上，我們把原式化簡成以下的樣子。

還記得我們的假設嗎，我們要求 \(i < \sqrt n\)
所以可以直接把 \(\log \frac{n}{i}\) 替換成 \(\log n\)。

綜上，我們得到了形如 \(pqr\) 的數的數量級為 \(\Theta \left( \frac{n \log^2 \log n}{\log n} \right)\)
雖然好像沒什么用......但是好像確實沒什么用。