백준 알고리즘 11653번: 소인수분해 [C++]

문제 출처: www.acmicpc.net/problem/11653

11653번: 소인수분해

1. 코드

#include <iostream>

using namespace std;

int main(void)
{
	int n;
	cin >> n;		//정수 n입력

	//n이 1이하일 경우에만 정지
	while (n > 1)	
	{
		for (int i = 2; i <= n; i++)	//2부터 n까지 반복
		{
			if (n % i == 0)				//반복 도중 n에 나누어 떨어지는 경우
			{
				n /= i;					//n을 i에 나눈 값을 저장
				cout << i << endl;		//소인수 분해 결과 = i 출력
				break;					//n의 크기 검사를 위해 반복 중지
			}
		}
	}
}

(실행)

2. 설명

먼저 정수 n의 값을 입력받는다.

int n;
cin >> n;		//정수 n입력

입력받은 n의 값이 1이하가 아니라면 즉, 2이상이면 while()문을 통해 계속해서 반복해준다.

//n이 1이하일 경우에만 정지
while (n > 1)	

그리고 또다시 while()문 안에 2부터 n까지 반복을 하는데 이 과정에서 소인수분해의 결과를 찾아낼 것이다. 2부터 시작하는 이유는 소인수분행의 결과는 2부터 있기 때문이다.

for (int i = 2; i <= n; i++)	//2부터 n까지 반복

그리고 반복문의 카운터 변수인 i의 값이 n을 나누어 떨어지게 만들 경우 n의 값을 i로 나눈 값을 n에 저장을 한 뒤 해당 i를 출력하고 반복문을 종료한다.

if (n % i == 0)				//반복 도중 n에 나누어 떨어지는 경우
{
	n /= i;					//n을 i에 나눈 값을 저장
	cout << i << endl;		//소인수 분해 결과 = i 출력
	break;					//n의 크기 검사를 위해 반복 중지
}

i를 출력하는 이유는 변수 i는 실질적으로 소인수분해의 결과이기 때문이다. 그리고 break를 통해 for문의 반복문을 정지한 이유는 해당 n의 값이 2이상인지 확인해야하며 만약 그렇다면 소수인분해 결과를 얻기 위해서 다시 2부터 n까지 반복을 해야하기 때문이다.