结论

因数个数

对于一个数 n，它的因数个数的数量级为 O(n13)。

小于 n 的质数个数

小于 n 的质数个数为 O(nlog⁡n)。

• 参考链接：这里

log换底公式

loga⁡b=logc⁡blogc⁡a

其中，c 为任意正数。

证明：

设 a=cx,b=cy，有

loga⁡b=logcx⁡cy=yxlogc⁡c=yx=logc⁡blogc⁡a

方法

求一个数的所有因数

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

例如：72=8×9=23×32，那么它的所有因子应该是：

(1)×(1,2,4,8)×(1,3,9)

其中，这个 × 符号代表 Cartesian Product。

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

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}