素因数分解のアルゴリズム

2020年3月1日数学エラトステネスの篩,素因数分解

素因数分解とは「ある自然数を素数の積の形に分解すること」です。

  • \(12 = 2^2 × 3\)
  • \(1024 = 2^{10}\)

1つの自然数 n を \(O(\sqrt{n})\) で素因数分解する方法と、複数の自然数を前処理 \(O(n \log \log n)\)、クエリ \(O(\log n)\) で素因数分解する方法の二種類を解説します。

アルゴリズム

素因数分解（前処理なし）：

  1. \(\sqrt{n}\) 以下の素数 p に対して以下を行う
    1. \(n\) を p で何回割り切れるかを保存しておく。また、\(n\) をその回数だけ p で割った数に変更する
  2. \(n\) が 1 にならなければ \(n\) は素数。そうでなければ、保存していた素数と割り切れる回数のペアが答え。

※ \(n\) が素数でなければ、2 以上 \(sqrt{n}\) 以下の数に約数が存在することを利用しています。

SPF を利用したアルゴリズム（前処理あり）：

  • 前処理
    1. エラトステネスの篩と同様のアルゴリズムで SPF を各数について求める
  • クエリ（\(n\) の素因数分解を求める）
    1. 以下を \(n\) が 1 になるまで繰り返す
      • \(n\) の SPF を 素因数の一つとして保存しておく
      • \(n\) を SPF で割った商を新たな \(n\) とする
    2. 保存しておいた素因数が、素因数分解になっている

※ SPF(Smallest Prime Factor)：各数に対する最小の素因数 のこと
※ エラトステネスの篩(素数の判定を参照) と同様のアルゴリズムによって、1 から \(n\) までの数の SPF を \(O(n \log \log n)\) の前処理で求めることができます。

計算量

  • 前処理なしのアルゴリズム
    • 前処理：なし
    • クエリ：\(O(\sqrt{n})\)
  • SPF を利用した前処理ありのアルゴリズム
    • 前処理：\(O(n \log \log n)\)
    • クエリ：\(O(\log n)\)

前処理なしのアルゴリズムの場合は、\(\sqrt{n}\) までの素数に対して行うので、\(O(\sqrt{n})\) だけ時間がかかります。

SPF を利用したアルゴリズムの場合は、\(n\) の素因数の数は \(O(\log n)\) 程度になっているので、その数だけ時間がかかります。

C++での実装例

前処理なしのアルゴリズム

/*  prime_factor(n)
    入力：整数 n
    出力：nの素因数分解
    計算量：O(√n)前後
*/
template <typename T>
vector<pair<T, T>> prime_factor(T n) {
    vector<pair<T, T>> ret;
    for (T i = 2; i * i <= n; i++) {
        if (n % i != 0) continue;
        T tmp = 0;
        while (n % i == 0) {
            tmp++;
            n /= i;
        }
        ret.push_back(make_pair(i, tmp));
    }
    if (n != 1) ret.push_back(make_pair(n, 1));
    return ret;
}

SPF を利用するアルゴリズム

構造体などにまとめると以下のようになります。

/*  PrimeFact
    init(N): 初期化。O(N log log N)
    get(n): クエリ。素因数分解を求める。O(log n)
 */
template <typename T>
struct PrimeFact {
    vector<T> spf;
    PrimeFact(T N) { init(N); }
    void init(T N) { // 前処理。spf を求める
        spf.assign(N + 1, 0);
        for (T i = 0; i <= N; i++) spf[i] = i;
        for (T i = 2; i * i <= N; i++) {
            if (spf[i] == i) {
                for (T j = i * i; j <= N; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
    }
    map<T, T> get(T n) { // nの素因数分解を求める
        map<T, T> m;
        while (n != 1) {
            m[spf[n]]++;
            n /= spf[n];
        }
        return m;
    }
};

Smallest Prime Factor(SPF) の気持ち

２つ目のアルゴリズムでは、Smallest Prime Factor(SPF) と呼ばれるものを利用します。これは、各数に対する最小の素因数(SPF) のことです。

SPF の前計算により \(O(1)\) で \(n\) の素因数 p を一つ取得することができます。

これを利用すると、例えば 48 の素因数分解は以下のように求めることができます。

  1. 48 の素因数の一つは 2
  2. 48/2 = 24 の素因数の一つは 2
  3. 24/2 = 12 の素因数の一つは 2
  4. 12/2 = 6 の素因数の一つは 2
  5. 6/2 = 3 の素因数の一つは 3
  6. 以上より、\(48 = 2^4 \times 3\)

練習問題

数学エラトステネスの篩,素因数分解