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

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++での実装例

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

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

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

Smallest Prime Factor(SPF) の気持ち

2つ目のアルゴリズムでは、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\)

練習問題