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

코드

#include <iostream>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

// 소수 목록을 저장할 벡터
vector<int> prime;

// 에라토스테네스의 체로 소수 계산
void sieve() {
    int max_limit = 316; // sqrt(100,000)
    vector<bool> is_prime(max_limit + 1, true);
    is_prime[0] = is_prime[1] = false; // 0과 1은 소수가 아님
    for (int i = 2; i * i <= max_limit; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= max_limit; i++) {
        if (is_prime[i]) prime.push_back(i);
    }
}

int main() {
    int tc;
    cin >> tc;

    sieve(); // 소수 미리 계산

    while (tc--) {
        int n;
        cin >> n;

        map<int, int> factors; // 소인수와 지수를 저장
        for (int p : prime) {
            if (p * p > n) break; // 소수의 제곱이 n을 초과하면 종료
            while (n % p == 0) {
                factors[p]++;
                n /= p;
            }
        }
        if (n > 1) { // 남은 n이 소수일 경우 처리
            factors[n]++;
        }

        // 결과 출력
        for (const auto& factor : factors) {
            cout << factor.first << " " << factor.second << '\n';
        }
    }

    return 0;
}

풀이

에라토스테네스의 체를 사용해서 소수를 구하고, 소인수분해하는 과정을 코드로 구현했다. 0ms인 코드도 있는 거 같던데 더 공부해봐야겠다. 참고로 위 코드는 8ms가 나온다. 입출력차이인가?

 

실험결과 FASTIO 코드 차이였던 걸로. 빠른 입출력을 사용하면 0ms가 나온다.