소인수분해 문제

양의 정수 N이 주어졌을 때, 이를 소수들의 곱으로 분해하는 문제입니다.
예: 60 = 2 × 2 × 3 × 5

입력 조건

• 하나의 정수 N (2 ≤ N ≤ 1,000,000,000)

출력 조건

• N의 소인수들을 오름차순으로 출력

예시

입력: 60
출력: 2 2 3 5

입력: 3
출력: 3

접근 방법

초보자들은 보통 2부터 N까지 반복문을 돌며 확인하지만, N이 최대 10억일 때는 시간 초과가 발생합니다.
핵심 아이디어: N의 소인수 중 √N보다 큰 값은 최대 1개만 존재할 수 있습니다. 따라서 2부터 √N까지만 탐색하면 됩니다.

구현 전략

1. 2부터 √N까지 반복하면서 i가 N을 나누는 동안 반복
2. 나누어 떨어질 때마다 i를 출력하고 N을 i로 나눔
3. 반복 종료 후 남은 N이 1보다 크면 그 값을 출력 (√N보다 큰 소인수)

코드 예시

방법 1: 벡터를 사용한 저장 후 출력 (공간 효율적)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    vector<int> factors;
    int temp = N;
    
    for (int i = 2; i * i <= N; ++i) {
        while (temp % i == 0) {
            factors.push_back(i);
            temp /= i;
        }
    }
    
    if (temp > 1) {
        factors.push_back(temp);
    }
    
    for (size_t i = 0; i < factors.size(); ++i) {
        cout << factors[i];
        if (i != factors.size() - 1) cout << " ";
    }
    cout << "\n";
    
    return 0;
}

방법 2: 즉시 출력 방식 (메모리 최적화)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    int temp = N;
    bool first = true;
    
    for (int i = 2; i * i <= N; ++i) {
        while (temp % i == 0) {
            if (!first) cout << " ";
            cout << i;
            temp /= i;
            first = false;
        }
    }
    
    if (temp > 1) {
        if (!first) cout << " ";
        cout << temp;
    }
    cout << "\n";
    
    return 0;
}

성능 분석

• 시간 복잡도: O(√N) - 최악의 경우 N이 소수일 때 √N까지 반복
• 공간 복잡도: O(1) (즉시 출력 방식) 또는 O(log N) (벡터 저장 방식)
• 10억(1,000,000,000)의 경우 √N ≈ 31,623이므로 매우 빠르게 동작