C++で素因数分解を行う方法は一つではなく、扱う整数の大きさや分解を行う回数によって、適切なアプローチが変わります。
そのため、まずは「どのような条件下で、どの手法を選ぶべきか」を理解することが重要です。
以下では、C++で一般的に用いられる素因数分解の考え方を、用途別に整理して解説します。
基本となる考え方：試し割りによる素因数分解
最も基本的な方法は、「小さい数から順番に割っていく」試し割りです。
整数は、もし合成数であれば必ず √n 以下の素因数を少なくとも一つ持つ、という性質があります。
この性質を利用し、2から始めて順番に割れるかどうかを調べていきます。
割れた場合は、その数で何回割れるか（指数）を数え、割れなくなるまで割り続けます。
その後も同様に次の数で割ることを繰り返します。
途中で対象の数が小さくなり、最後に 1 より大きい数が残った場合、それは必ず素数であり、最後の素因数となります。
この方法はアルゴリズムとして非常に直感的で、1回だけ分解する用途であれば十分に実用的です。
計算量と適用範囲
試し割り法の計算量は、おおよそ √n に比例します。
そのため、対象となる整数が 10^12 程度までであれば、1回〜数回の分解なら問題なく処理できることが多いです。
一方で、対象が大きな素数に近い場合は、最悪ケースとして √n 回の判定が必要になります。
この点を踏まえると、「入力が大きく、回数も多い」場合には別の工夫が必要になります。
高速化の基本：2を特別扱いし、奇数のみを試す
試し割りの簡単な高速化として、2だけを特別に処理し、それ以降は奇数のみを調べる方法があります。
偶数は必ず 2 を素因数に持つため、2で割れるだけ割った後は、3・5・7…といった奇数だけを試せば十分です。
これにより、無駄な偶数チェックを省くことができ、実行時間をほぼ半分程度に削減できます。
この方法は実装も簡単で、実用上もっともよく使われる試し割りの形と言えます。
大量の数を分解する場合：最小素因数（SPF）を使う方法
分解対象の数が比較的小さく（例：10^7 程度まで）、かつ分解を何度も行う場合には、毎回試し割りを行うのは非効率です。
このようなケースでは、あらかじめ 各整数が持つ最小の素因数（Smallest Prime Factor, SPF） を前処理で求めておく方法が有効です。
SPFを一度計算しておけば、任意の数について「その数を割り切る最小の素数は何か」を即座に取得できます。
これを繰り返すことで、分解対象の数はどんどん小さくなり、結果として素因数分解は 素因数の個数に比例する時間で完了します。
理論上は高々 log₂(n) 回程度の処理で済むため、非常に高速です。
ただし、この方法は 前処理として最大値までの配列を確保する必要があるため、対象の最大値が大きすぎる場合にはメモリ面で不利になります。
64bit整数（〜10^18級）を扱う場合の注意点
対象となる整数が 10^18 近くになると、試し割り法は現実的ではありません。
√10^18 は 10^9 であり、これをそのまま試すのは実行時間的に不可能です。
このような大きな整数に対しては、以下の手法が一般的に用いられます。
- Miller–Rabin 素数判定
- Pollard’s Rho 法による素因数探索
これらを組み合わせることで、64bit整数であっても高速に素因数分解が可能になります。
特に 64bit 範囲に限定すれば、Miller–Rabin は決定的に素数判定できることが知られており、競技プログラミングや実務でも広く使われています。
ただし、これらの手法は実装が複雑になりがちなため、「本当に必要な場合にのみ採用する」という判断が重要です。
実装上の注意点と落とし穴
素因数分解を実装する際には、いくつか注意すべき点があります。
- 1 は素因数を持たないため、分解結果は空になります
- 0 は通常の意味で素因数分解が定義できないため、事前に除外する必要があります
- 負の数を扱う場合は、「-1 を因数として含めるかどうか」など、仕様を明確にする必要があります
- 「p × p ≤ n」という条件は、数値が大きい場合にオーバーフローする可能性があるため、より安全な比較方法を用いるのが望ましいです
これらを意識することで、バグや想定外の挙動を防ぐことができます。
手法選択の目安まとめ
用途別の目安としては、以下のように考えると分かりやすいでしょう。
- 数がそれほど大きくなく、分解回数も少ない
→ 試し割り（2を特別扱いした方法） - 比較的小さい数を大量に分解する
→ 最小素因数（SPF）による前処理 - 64bit整数を高速に分解したい
→ Miller–Rabin + Pollard’s Rho
このように、C++での素因数分解は「1つの正解」があるわけではなく、入力条件に応じて最適な手法を選ぶことが重要です。
目的に合った方法を選べば、実装も性能も無理のないものになります。
以上、C++での素因数分解についてでした。
最後までお読みいただき、ありがとうございました。
