[C++] 백준 BOJ 11653 소인수분해

문제링크 : https://boj.kr/11653

어떤 숫자의 소인수들은 소수들의 곱으로 표현할 수 있다.

그러기 위해선 입력 숫자의 범위만큼 소수 리스트를 구해서 해당 소수들이 입력 숫자로 나누어 떨어지는지를 계산하고 이를 무한히 반복하여 더이상 나누어 떨어지지 않을 때까지 나누면 된다.

다만, 소수 리스트를 다 구할 필요는 없고 입력 숫자의 제곱근 범위까지만 구하면 된다.

제곱근보다 큰 범위의 숫자를 2개 이상 서로 곱하면 입력 숫자를 초과하기 때문에 더 이상 구할 필요가 없다.

소수 리스트에 속하지 않은 남은 숫자는 무조건 소수이다. (해당 숫자가 소수 리스트의 곱으로 표현되는 순간 소수가 아니다.)

소수 판별은 에라토스테네스의 체를 이용하여 구하면 더 빠르게 구할 수 있다.

// BOJ 11653 소인수분해
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
 
    int input;
    cin >> input;
 
    // 입력이 1일 경우 연산하지 않고 바로 종료
    if (input == 1) return 0;
    
    // 에라테네스의 체 이용하여 소수 리스트 만들기
    // 소수를 판별할 리스트는 최대 input의 루트 값까지
    int maxNum = sqrt(input) + 1;
    vector <bool> isPrime(maxNum + 1, false);
    vector <int> pnum;
    
    for (int i = 2; i <= maxNum; i++)
        isPrime[i] = true;
 
    for (int i = 2; i <= maxNum; i++) {
        if (isPrime[i]) {
            pnum.push_back(i);
            for (int j = i * 2; j <= maxNum; j += i)
                isPrime[j] = false;
        }
    }
    
    for (int i = 0; i < pnum.size(); i++) {
        while (input % pnum[i] == 0) {
            input /= pnum[i];
            cout << pnum[i] << "\n";
        }
    }
    // 소수 리스트에 없는 수가 남았을 때 == 소수 (자기자신 포함)
    if (input > 1)
        cout << input << "\n";
    
    return 0;
}