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

문제

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

접근 방법

N이 최대 10,000,000이기에 2부터 차례대로 확인해 보는 방식으로도 문제없습니다.

코드

#include <iostream>
using namespace std;

int N;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;

    int num = N;

    for (int i = 2; i * i <= N && num != 1; ++i)
    {
        while (num % i == 0)
        {
            cout << i << "\n";
            num /= i;
        }
    }

    if (num == 1)
    {
        return 0;
    }
    cout << num;
    return 0;
}

풀이

2부터 N까지 확인하는 방법을 사용하면 소수인 N이 들어왔을 때 2부터 N-1까지의 불필요한 반복을 하게 됩니다.

제곱근을 넘는 소인수는 존재하지 않으므로 제곱근까지만 확인하는 방법으로 해결할 수 있습니다.