[백준 16563] 어려운 소인수분해 구하기 (C++)

📕문제

지원이는 대회에 출제할 문제에 대해서 고민하다가 소인수분해 문제를 출제해야겠다고 마음을 먹었다. 그러나 그 이야기를 들은 동생의 반응은 지원이의 기분을 상하게 했다.
"소인수분해? 그거 너무 쉬운 거 아니야?"
지원이는 소인수분해의 어려움을 알려주고자 엄청난 자신감을 가진 동생에게 2와 500만 사이의 자연수 N개를 주고 소인수분해를 시켰다. 그러자 지원이의 동생은 기겁하며 쓰러졌다. 힘들어하는 지원이의 동생을 대신해서 여러분이 이것도 쉽다는 것을 보여주자!

---

📕입력

첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다.

---

📕출력

N 줄에 걸쳐서 자연수 ki의 소인수들을 오름차순으로 출력하라.

---

📗예제 입력 

5
5 4 45 64 54

📗예제 출력 

5
2 2
3 3 5
2 2 2 2 2 2
2 3 3 3

 

시간 복잡도에 굉장히 신경을 써야 하는 문제이다.

나도 계속 시간초과가 떠서 고생했다..ㅠ

 

문제 자체는 정말 쉽다.처음에는 

• 수를 2로 나누고 2로 못 나눈다면 3으로 나누고 ,,, 그렇게 해서 √n까지 했다.
  • 시간 초과가 발생.

그 다음 생각해본 게 소인수들의 배수인 수를 소인수로 초기화한다.

예를 들어 ary[4]=2, ary [9]=3, ary [16]=2, ary [24]=2 

이런 식으로 초기화해준다면 

24를 ary[24]로 나누고 그 나눈 몫을 또다시 ary안에 있는 값으로 나눠준다면 될 거 같았다.

 

이해하기 쉽게 예를 하나 들겠다.

• 만약 내가 구하고 싶은 숫자가 45라고 하자.
• 45의 가장 작은 소인수는 3이다.
• 그러면 ary [45]=3이 될 것이다.
• 그러면 45를 ary [45]의 값으로 나눈다. 그리고 ary [45] 값을 출력한다.
  • 그러면 3이 출력되고 숫자는 15가 될 것이다. 다시 15를 ary[15]로 나누고 ary[15]를 출력
  • 그러면 3이 출력되고 숫자는 5가 될것이다. 다시 5를 ary [5]로 나누고 ary [5]를 출력
  • 그러면 숫자는 1이 되기 때문에 종료한다.
• 이것보다 더 좋은 방법이 있을 거 같은데 시간 초과를 해결할 방법이 없는 것 같다.

📗코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
#define Max 5000000
vector<int> include(Max + 1);
int main()
{
 	ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    scanf("%d", &N);
    //int num = 0;
    int max = 0;
    vector<int>num(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> num[i];
        if (max < num[i])
            max = num[i];
    }
    for (int i = 0; i <= max; i++)
    {
        include[i] = i;
    }
    for (int j = 2; j <= sqrt(max); j++)
    {
        if (include[j] == j) //include[j]==j는 j가 소수라는 뜻이다.
        {
            for (int k = j * j; k <= max; k += j)
            {
                //include[k]==k는 아직 값을 넣기 전이다. 가장 작은 소인수로 넣어줘야하기때문에 값을 넣어줬다면 다시는 넣어주지않는다.
                if (include[k] == k)            
                    include[k] = j;
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        while (1)
        {
            if (num[i] == 1)
            {
                break;
            }       
            printf("%d ", include[num[i]]);
            num[i] = num[i] / include[num[i]];
        }
        printf("\n");
    }
}

---

👀느낀 점

 시간 초과는 진짜 짜증 난다.

ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

원래 코드에서 3줄만 추가하니까 시간 초과가 없어졌다. 물론 수정한 코드에서는 위 3줄이 없어도 돌아갔지만, 

초기 코드에서 3줄을 추가하니까 시간초과가 없어져서 굉장히 황당했다.