백준 11653번 - 소인수분해 / C++

1. 문제

문제 링크

---

2. 풀이

소인수분해

소인수분해(영어: prime factorization, integer factorization)는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

소수로 N을 반복해서 분해하며 분해될 때마다 해당 소수를 출력한다.
N을 소수로 나누고 N이 1이 되기 전까지 나누면 된다.
->N이 1보다 크다면 계속 반복한다.

while(N > 1)
{
	// N을 소수로 나눈다.
    N = N / 소수;
}

최종적으로 N 자체가 소수가 되어 자기 자신으로 나누어지면
N은 1이 되고 루프를 탈출하게된다.

---

오름차순으로 출력한다.

(1) 출력할 소수는 정의 자체가 1보다 큰 수이므로 2부터 시작하면 된다.

(2) 자기 자신이 약수가 되므로 N이 될 때까지 반복한다.

(3) 오름차순이므로 출력 후 다시 2부터 시작해야한다.

while(N > 1)
{
    for(int i = 2 ;  // (1)
            i <= N ; // (2)
            i++)
    {
		if(N%i == 0)
        {
        	cout << i << "\n";
            N /= i;
            break;   // (3)
        }
    }
}

N이 1인 경우 아무것도 출력하지 않는다.

while(N > 1) 조건에 이미 포함되어있다.

---

3. 코드

#include <iostream>

using namespace std;

int main()
{
    int N;
    cin >> N;
    while(N > 1)
    {
        for(int i = 2 ; i <= N ; i++)
        {
            if(N%i == 0)
            {
                cout << i << "\n";
                N /= i;
                break;
            }
        }
    }

    return 0;
}

---

참고 자료

소인수분해 - 위키백과
https://ko.wikipedia.org/wiki/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4