[BOJ_C++] 2312번 : 수 복원하기

1. 문제

2. 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

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

    int t, n, temp; cin >> t;
    int result[100001];
    for (int tc = 0; tc < t; tc++) {
        cin >> n; temp = n;
        memset(result, 0, sizeof(result));
        for (int i = 2; i <= n; i++) {
            while (temp % i == 0) {
                ++result[i];
                temp /= i;
            }
        }
        for (int i = 2; i <= n; i++) {
            if (result[i]) printf("%d %d\n", i, result[i]);
        }
    }


    return 0;
}

• 최대 수가 100,000이기 때문에 100,001 크기의 배열을 선언하고 테스트 케이스마다 배열의 값을 0으로 초기화 해 주었다.
• i는 2부터 n까지 for문을 돌며 temp가 i로 나눈 나머지 값이 0일 때 반복하여 result[i]의 값을 1 증가시키고 temp를 i로 나눠준다.
• temp를 i로 나눈 나머지가 0일때 카운트 수를 증가시키는 이유는 나눈 나머지가 0이라는 것이 소인수분해가 된다는 뜻이기 때문이다.
• i는 2부터 n까지 for문을 돌며 result[i]에 값이 존재할 때 i와 result[i]의 값을 출력한다.

3. 결과