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

 

https://www.acmicpc.net/problem/2312

 

 

 

#문제 간단 정리

 

N을 소인수분해한 결과를 출력

 

 

#문제 해결 방법

 

우선 첫째로 소인수 분해를 하기 위해

소수들로 나눠줘야 하는데

 

그렇기 때문에 1. 소수를 구해야 한다

 

소수를 구하는 방법은 여러가지 방법이 있지만

브루트포스로 1부터 N까지 소수를 구하거나 하면 너무 시간이 오래 걸리니

에라토스테네스로 소수를 구해서 

소수들만 따로 구해주도록한다.

 

그렇다면 이제 주어진 수를 소수로 나누고 개수를 카운팅해야된다

2. 소수로 나누고 개수를 카운팅해야된다

에라토스테네스의 체로 구한 소수들로 계속해서 나눠서 소인수분해한 결과를

담는 것은 어렵지 않다.

 

그런데 만약에 2x2x3 이렇게 되있다면 2가 두번 중복 되기 때문에

2 2 이렇게 (숫자) (개수) 로 한번에 출력해야 되기 때문에

나는 map 을 사용해서 map에 이미 존재한다면 map 의 키 값을 증가시켜줘 

개수를 세어줬다.

 

 

#전체 코드

 

에라토스테네스의 체는 https://dfdfg42.tistory.com/entry/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4-C-%EC%BD%94%EB%93%9C

에라토스테네스의 체 C++ 코드

를 참고하도록 하자(모른다면)

 

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>

using namespace std;


const int MAX = 100'000;

bool check[MAX + 1];
vector<int> primes;
vector<int> factors;

void Factorization(int num) {

    for (int i : primes) {
        if (num % i == 0) {
            factors.push_back(i);
            Factorization(num / i);
            break;
        }
    }

    return;
}

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



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

        if (check[i] == false) {
            primes.push_back(i);

            for (int j = i; j <= MAX; j += i) {
                if (check[j] == false) {
                    check[j] = true;

                }
            }
        }

    }


    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        int a;
        cin >> a;


        Factorization(a);

        map<int, int> factorCount;
        for (int f : factors) {
            if (factorCount.find(f) != factorCount.end()) {
                factorCount[f]++;
            }
            else {
                factorCount[f] = 1;
            }
        }

        for ( auto& pair : factorCount) {
            cout << pair.first << " " << pair.second << '\n';
        }

        factors.clear();
        factorCount.clear();
    }

    return 0;
}