[C++] 소인수분해 : 11653번

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.  N이 1인 경우 아무것도 출력하지 않는다.

---

예제 입력

72

예제 출력

2
2
2
3
3

---

해석

어떤 수 N을 소인수 분해한다는 것은 소수들의 곱으로만 이루어지도록 만드는 것을 의미한다.

따라서 가장 작은 소수 2부터 나누어 떨어진다면 소인수분해를 1차례 진행한 것이다.

 

반복적으로 2 와 N - 1 사이까지 나누면서 나누어 떨어지는 시점이 발생하면,

나누어서 얻은 새로운 몫인 N 과 새로운 연산을 하며 N이 더이상 나누어지지 않을 때 까지 진행하면 된다.

 

마지막으로는, 최종으로 남은 N 까지 출력하면 소인수분해가 완료된다.

 

풀이

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int N; // 주어지는 정수
	int divider = 2; // 시작 위치
	cin >> N;

	if (N == 1) return 0; // 1일 경우 아무것도 출력 안함
	for (divider; divider < N; divider++) // 나누는 수 2 ~ N-1 
	{
		if (N % divider == 0) // 나누어 떨어지면
		{
			N = N / divider; // 나눈 몫 다시 대입
			cout << divider << "\n"; // 소수 출력
			divider = 1; // 나누는 수 초기화
		}
	}
	cout << N; // 마지막 남은 몫까지 출력
}