C++에서 n을 k개의 곱으로 작성할 수 있는지 확인

숫자 N이 있다고 가정합니다. 또 다른 숫자 k가 있습니다. k 개의 숫자를 사용하여 숫자를 나타낼 수 있는지 여부를 확인해야 합니다. 숫자가 54이고 k =3이라고 가정하면 [2, 3, 9]와 같은 숫자가 인쇄되고, 표현할 수 없으면 인쇄합니다.

이를 해결하기 위해 N의 모든 소인수를 찾아 벡터에 저장한 다음 1보다 큰 k 숫자를 찾기 위해 벡터의 크기가 k보다 큰지 확인합니다. 크기가 k보다 작으면 -1을 반환하고, 그렇지 않으면 처음 k-1 인수를 인쇄하고 마지막 인수는 나머지 모든 숫자의 곱이 됩니다.

예시

#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; //reduce n by dividing this by 2
   }
   for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
      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