백준 2312번 수 복원하기 c++ 풀이

문제

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2 ≤ N ≤ 100,000)이 주어진다.

출력

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

예제 입력 1 복사

2
6
24

예제 출력 1 복사

2 1
3 1
2 3
3 1

 

소인수분해를 이용하여 2부터 시작해서 나누고 만약에 나머지가 0이면 계속해서 나누고 0이 아니라면 2++를 해서 또 반복해 준다.

 

 

- c++ 풀이

#include <bits/stdc++.h>

using namespace std;

int t;
int n;

int arr[100001];


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

    cin >> t;

    while (t--) {
        memset(arr, 0, sizeof arr);
        cin >> n;
        int temp = n;

        for (int i = 2; i <= n; i++) {
            while (temp % i == 0) {
                temp /= i;
                arr[i]++;
            }
        }

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

            if (arr[i] > 0) {
                cout << i << " " << arr[i] << "\n";
            }


        }


    }

    return 0;
}