数量估计

质数的数量估计

不超过 $n$ 的质数个数大概是 $O\left(\frac{n}{\log n}\right)$ 个。

Mertens 第二定理

$$\sum _{p⩽n}\frac{1}{p}=O(\log \log n).$$

相关结论：

1. 枚举范围 $n$ 以内每个数的倍数的复杂度是 $O(n\log n)$
2. 枚举范围 $n$ 以内每个数的质数倍的复杂度是 $O(n\log \log n)$

数论分块结论

$\left\{\lfloor \frac{n}{i}\rfloor :1⩽i⩽n\right\}$ 的元素个数是 $O(\sqrt{n})$