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

• 문제

 

• 풀이

#include <iostream>
using namespace std;

int main()
{
	int n = 0;

	cin >> n;

	while (true)
	{
		if (n == 1)
		{
			break;
		}

		for (int i = 2; i <= n; i++)
		{
			// 그냥 if문으로 체크하면 한번 체크된 값 이후로 더 큰 값들을 계속 체크하므로
			// 중복한 i 값 ex. 2 -> 2가 나올 수 없는 경우가 생김
			// 따라서 소인수에 해당하는 값이 나오면 break를 해서
			// 다음 체크로 넘어가거나 if 대신 while(n % i == 0)을 사용해야 한다.
			if (n % i == 0)
			{
				cout << i << endl;
				n /= i;
				break;
			}
		}
	}

	return 0;
}

 

• 메모

소인수분해가 되려면 해당 값으로 N을 나머지 연산했을 때 값이 0이 되면서 가장 작은 값이여야 한다.
이때 1은 소수가 아니기 때문에 2부터 N까지의 수를 나눠준다.

 

만약 if문을 사용하는 경우 목표 숫자를 찾았을 때 연산을 중간에 멈춰주지 않으면

가장 작은값에 해당하는 소수가 중복되서 나올 수 없는 경우가 생기기 때문에 반드시 break문을 사용한다.

 

또는 while문을 사용해 나머지 연산 결과가 0인 경우를 조건으로 넣어주는 방법도 있다.