codewars Factorial decomposition

문제 링크입니다: https://www.codewars.com/kata/factorial-decomposition/train/cpp

완전탐색법을 통해 푼 문제였습니다.

시간 단축을 위해 vector<pair<int, int>> v를 선언하여 first에는 n 이하 자연수, second에는 지수가 저장되도록 하였습니다.

/*

주어진 N을 소인수 분해하시오

*/

#include <iostream>

#include <vector>

#include <string>

using namespace std;

 

std::string decomp(int n) {

        //your code here

        string result;

        vector<pair<int, int>> v(n + 1, make_pair(0, 0));

        for (int i = 1; i <= n; i++)

               v[i].first += i; //n 이하 자연수 저장

 

        for (int i = 2; i <= n; i++)

        {

               int temp = i;

               for (int j = 2; j <= i; j++)

               {

                       int cnt = 0;

                       while (temp % j == 0)

                       {

                              cnt++;

                              temp /= j;

                       }

                       if (cnt)

                              v[j].second += cnt; //해당 소수가 나누어진다면 지수를 더해준다

               }

        }

        for (int i = 2; i < v.size(); i++)

        {

               int first = v[i].first;

               int cnt = v[i].second;

               if (cnt) //나누어진 소수라면

               {

                       //결과 string에 더해준다

                       result += to_string(v[i].first);

                       if (cnt >= 2)

                       {

                              result += "^";

                              result += to_string(cnt);

                       }

                       result += " * ";

               }

        }

        if (result.size() > 3)

               for (int i = 0; i < 3; i++)

                       result.pop_back(); //마지막 곱하기는 없어야하므로 없애준다

        return result;

}

 

int main(void)

{

        cout << decomp(5) << endl << endl;

        cout << decomp(14) << endl << endl;

        cout << decomp(17) << endl << endl;

        cout << decomp(22) << endl << endl;

        cout << decomp(25) << endl << endl;

        cout << decomp(79) << endl << endl;

        cout << decomp(98) << endl << endl;

        cout << decomp(3988) << endl << endl;

        /*

        cout << decomp(3989) << endl << endl;

        cout << decomp(3990) << endl << endl;

        */

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~