[백준 2312번] 수 복원하기 (C++)

문제링크 : https://www.acmicpc.net/problem/2312

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

int N, num;

int main() 
{
    cin >> N;
    while(N--)
    {
        map<int, int>m;
        cin >> num;
        int tmp = num;
        for(int i=2; i*i<=num; i++)
        {
            while(tmp%i==0)
            {
                m[i]++;
                tmp/=i;
            }
        }

        if (tmp > 1) m[tmp]++;

        for(auto i : m)
        {
            cout << i.first << " " << i.second << "\n";
        }
    }

    return 0;
}

 

소인수 분해를 하고, 이때 소인수의 개수를 같이 출력하는 문제이다.

반복문 i=2부터 시작하여 현재 입력받은 num을 나눌 수 있을 때까지 반복하여 나눠주며 map을 활용해 사용된 개수를 카운팅한다.

이를 i*i<=num 범위까지 반복하여 가능한 모든 소인수를 구해준다.

주의할점은 마지막 소인수를 놓칠 수 있기에, 나누고 남은 결과값 tmp에 대해서 1보다 크다면 추가적인 카운팅을 해주어야 한다.