结论

因数个数

对于一个数 $n$，它的因数个数的数量级为 $O(n^{\frac{1}{3}})$。

小于 $n$ 的质数个数

小于 $n$ 的质数个数为 $O(\frac{n}{\log n})$。

• 参考链接：这里

log换底公式

$$\log_a b = \frac{\log_c b}{\log_c a}$$

其中，$c$ 为任意正数。

证明：

设 $a = c^x, b = c^y$，有

$$\log_a b = \log_{c^x} c^y = \frac{y}{x}\log_c c = \frac{y}{x} = \frac{\log_c b}{\log_c a}$$

方法

求一个数的所有因数

先质因数分解，得到一个 map<ll, int> mp 代表每个质因数和它对应的 cnt，然后根据质因数分类后乘在一起即可。

例如：$72=8 \times 9=2^3 \times 3^2$，那么它的所有因子应该是：

$$(1) \times (1, 2, 4, 8) \times (1, 3, 9)$$

其中，这个 $\times$ 符号代表 Cartesian Product。

• 这样就无需去重了，很方便。

代码 
map<ll, int> mp;  // 这里已经储存了质因数和对应的 cnt
vector<ll> get_div() {
    vector<ll> res = {1};
    for (auto [p, cnt] : mp) {
        ll cur = 1;
        vector<ll> tmp;
        for (int i = 0; i <= cnt; i++) {
            for (ll x : res)
                tmp.push_back(x * cur);
            cur *= p;
        }
        res = tmp;
    }
    sort(res.begin(), res.end());
    return res;
}