C++で整数の因数の組み合わせをすべて求める方法

ある整数が与えられたとき、その数は複数の因数（因子）の積として表すことができます。例えば、8 = 2 × 2 × 2 = 2 × 4 のように表せます。本記事では、整数 n を受け取り、その因数のすべての組み合わせを返す関数を C++ で実装する方法を解説します。

例えば、入力が 12 の場合、出力は [[2, 6], [2, 2, 3], [3, 4]] となります。なお、n 自身だけを要素とする組み合わせ（例：[12]）は結果に含めないのが一般的です。

アルゴリズムの考え方

この問題は再帰（バックトラッキング）を使うことで効率的に解けます。手順は以下の通りです。

• solve() 関数を定義します。引数は n（現在の値）、target（元の数）、start（探索開始の因数）です。
• 結果を格納する二次元のリスト ret を用意します。
• n が 1 になったら、ret をそのまま返します。
• n が target と等しくない場合（つまり元の数そのものではない場合）、n 単体を 1 つの組み合わせとして ret に追加します。
• i を start から始め、i × i ≤ n である間ループします。
  • n を i で割り切れる場合、solve(n / i, target, i) を再帰呼び出しして other を取得します。
  • other の各組み合わせに対して i を末尾に追加し、それを ret に加えます。
• 最後に ret を返します。
• メイン側からは solve(n, n, 2) を呼び出します。start を 2 から始めることで、1 や n 自身を因数として扱うことを防ぎます。

ポイントは「i × i ≤ n」までしか探索しない点です。これにより、i と n / i の両方をカバーでき、重複した組み合わせの生成を避けられます。また、再帰呼び出し時に start に i を渡すことで、因数が昇順に並ぶことが保証されます。

実装例

以下に C++ での実装例を示します。

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

void print_vector(vector<vector<int>> v){
   cout << "[";
   for(int i = 0; i < v.size(); i++){
      cout << "[";
      for(int j = 0; j < v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]" << endl;
}

class Solution {
public:
   vector<vector<int>> solve(int n, int target, int start){
      vector<vector<int>> ret;
      if(n == 1){
         return ret;
      }
      if(n != target){
         ret.push_back({n});
      }
      for(int i = start; i * i <= n; i++){
         if(n % i == 0){
            vector<vector<int>> other = solve(n / i, target, i);
            for(int j = 0; j < other.size(); j++){
               other[j].push_back(i);
               ret.push_back(other[j]);
            }
         }
      }
      return ret;
   }
   vector<vector<int>> getFactors(int n) {
      return solve(n, n, 2);
   }
};

main(){
   Solution ob;
   print_vector(ob.getFactors(16));
}

入力

16

出力

[[8, 2], [4, 2, 2], [2, 2, 2, 2], [4, 4]]

処理の流れの解説

入力が 16 の場合、処理は次のように進みます。

• まず solve(16, 16, 2) が呼び出されます。
• i = 2 のとき、16 % 2 == 0 なので solve(8, 16, 2) を再帰呼び出しします。ここから [8, 2]、さらに再帰的に [4, 2, 2]、[2, 2, 2, 2] が得られます。
• i = 4 のとき、16 % 4 == 0 なので solve(4, 16, 4) を呼び出し、[4, 4] が得られます。
• これらすべてが統合され、上記の出力結果となります。

このように再帰とバックトラッキングを組み合わせることで、重複のない因数の組み合わせをすべて列挙できます。計算量は因数の個数に依存しますが、平方根までの探索に限定することで無駄を大幅に削減できるのが特徴です。