백준 11653 - 소인수분해

문제

 

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

11653번: 소인수분해

 

 

풀이

 

소인수분해는 소수들의 곱을 이용해서 정수를 나타내는 방법이다.

 

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4

소인수분해 - 위키백과, 우리 모두의 백과사전

 

N 보다 작은 소수들을 먼저 구하려고 했지만 그럴 필요가 없는 문제이다.

 

소수가 아닌 수들은 결국 앞에 나온 소수들의 곱으로 이루어지게 되므로, N을 2부터 시작해서 나누었을 때 나머지가 없으면 그 수는 N을 이루는 소수가 된다.

 

예를 들어 N = 80의 경우

80 % 2 = 0 -> N = 40,

40 % 2 = 0 -> N = 20,

20 % 2 = 0 -> N = 10,

10 % 2 = 0 -> N = 5,

5 % 2 = 1 -> N = 5,

5 % 3 = 2 -> N =5,

5 % 4 (4는 2*2 로 표현되므로 건너뜀, 2로 나눌 때 이미 계산이 끝난 경우)

5 % 5 = 0 -> N = 1

 

이렇게 N = 1 이 되면 소인수분해가 종료된다.

 

 

코드

 

#include <iostream>
 
using namespace std;
 
int N;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N;
 
    if (N == 1) return 0;
 
    int tmp = 2;
    while (N != 1)
    {
        if (N % tmp) tmp++;
        else
        {
            N /= tmp;
            cout << tmp << '\n';
        }
    }
 
    return 0;
}