[백준 11653] 소인수분해

에라토스테네스의 체로 미리 소수를 다 구한다음에 진행해도 되고

아래와 같이 그냥 무지성으로 계속 나눠봐도 된다.

 

이때 sqrt(N) + 1까지만 돌리면 된다.

이 범위 이상에서 인수가 나올 수 없다고 한다.

 

---

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;

    int x = sqrt(N) + 1;

    for (int i = 2; i <= x; i++)
    {
        while (N % i == 0)
        {
            cout << i << "\n";
            N /= i;
        }
    }

    if (N > 1)
    {
        cout << N;
    }

    return 0;
}