競プロノート

Appearance

素因数分解（Prime Factorization） ​

整数Nを素数の積に分解し、各素因数とその指数を求める。

特徴 ​

項目内容
用途素因数と指数の取得
計算量O(√N)
空間計算量O(log N)
前処理不要

考え方 ​

2から√Nまでの整数で、割り切れるだけ割っていく。

例えば、

360 = 2³ × 3² × 5

なので、結果は

text
(2, 3), (3, 2), (5, 1)

となる。

最後に1より大きい数が残れば、その数も素因数として追加する。

実装 ​

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<pair<ll, int>> prime_factorize(ll n) {
    assert(n >= 1);
    vector<pair<ll, int>> res;
    for (ll p = 2; p <= n / p; p += (p == 2 ? 1 : 2)) {
        if (n % p != 0) continue;
        int e = 0;
        while (n % p == 0) n /= p, e++;
        res.emplace_back(p, e);
    }
    if (n > 1) res.emplace_back(n, 1);
    return res;
}

int main() {
    ll n;
    cin >> n;
    for (auto [p, e] : prime_factorize(n)) cout << p << ' ' << e << '\n';
}

使用例 ​

入力

text
360

出力

text
2 3
3 2
5 1

返り値は vector<pair<ll, int>> で、{素因数, 指数} を昇順に格納する。

cpp
auto factors = prime_factorize(360);
// {{2, 3}, {3, 2}, {5, 1}}

典型的な応用 ​

約数の個数 ​

Nの素因数分解が

N = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ

のとき、約数の個数は

(e₁ + 1)(e₂ + 1)...(eₖ + 1)

で求められる。

cpp
ll cnt = 1;
for (auto [p, e] : prime_factorize(n)) cnt *= e + 1;

例えば360の約数の個数は

(3+1)(2+1)(1+1) = 24

となる。

異なる素因数の個数 ​

cpp
int cnt = prime_factorize(n).size();

素因数の個数（重複込み） ​

cpp
int cnt = 0;
for (auto [p, e] : prime_factorize(n)) cnt += e;

注意点 ​

  • Nは1以上とする。
  • N=1の場合、返り値は空。
  • p*p <= n の代わりに p <= n/p とすることでオーバーフローを防ぐ。
  • 試し割りでは素数以外の整数を試しても問題ない。
  • 割るたびにNを小さくすることで、探索を早められる。
  • 多数の整数を素因数分解する場合はSPF（最小素因数）が有効。
  • 10^18程度の巨大な整数に試し割りを使うのは現実的ではない。

関連 ​