素因数分解について

前々から書く時ちょっと迷うことがあったのでメモ。

整数 の素因数分解を O() でやります。

void calc(ll x, map<ll, int>& M) {
    for (ll i = 2; i*i <= x; i++) {
        int cnt = 0;
        while (x%i == 0) {
            x /= i;
            cnt++;
        }
        if (cnt) M[i] += cnt;
    }
    if (x > 1) M[x] += 1;
}