C++で数Nをk個の数の積として表現できるかどうかを判定する方法

数Nと整数kが与えられたとき、Nをk個の数（1より大きい数）の積として表現できるかどうかを判定する方法を解説します。例えば、N=54、k=3が与えられた場合、54 = 2 × 3 × 9 と分解できるため「2, 3, 9」のように出力します。表現できない場合は、その旨を出力します。

アルゴリズムの考え方

この問題を解くには、まずNのすべての素因数を求め、それらをvectorに格納します。1より大きいk個の数を得るには、vectorのサイズがk以上であるかを確認します。サイズがk未満の場合は「-1」を返して表現不可を示します。サイズがk以上であれば、最初のk-1個の因数をそのまま出力し、最後の数は残りの因数すべての積とします。

例えば54を素因数分解すると 2 × 3 × 3 × 3 となり、素因数は4個あります。k=3の場合、最初の2個（2, 3）を出力し、残りの因数（3 × 3 = 9）を積として最後の数にします。この方法により、常にk個の数でNを表現できます。

サンプルコード

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int getKFactors(int n, int k){
   int i;
   vector<int> vec;
   while(n % 2 == 0){
      vec.push_back(2);
      n = n/2; //2で割り続けてnを減らす
   }
   for(i = 3; i <= sqrt(n); i=i+2){ //2ずつ増やして奇数のみを判定
      while(n % i == 0){
         n = n/i;
         vec.push_back(i);
      }
   }
   if(n > 2){
      vec.push_back(n);
   }
   if(vec.size() < k){
      cout << "Cannot be represented";
      return -1;
   }
   for (int i=0; i<k-1; i++)
   cout << vec[i] << ", ";
   int prod = 1;
   for (int i=k-1; i<vec.size(); i++)
   prod = prod*vec[i];
   cout << prod << endl;
}
int main() {
   int n = 54, k = 3;
   getKFactors(n, k);
}

出力結果

2, 3, 9

このコードでは、まず2で割り切れる間は2を因数として追加し、その後3から√Nまでの奇数で割り切れる間、因数として追加していきます。最後に2より大きい数が残っていれば、それも素因数としてvectorに加えます。素因数の個数がk未満であれば表現できないため「-1」を返し、十分な個数があれば最初のk-1個と残りの積を出力します。