読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

素因数分解について

アルゴリズム

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

整数  N素因数分解を O( \sqrt{N}) でやります。

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;
}