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

문제 풀이

소인수 분해를 어떻게 하는지에 대해 서임. 꽤나 유의미한 문제라고 생각됨.

풀이에서 크게 배울점은 while문과 while문 안에서 if-break문 사용하는 것임.

 

실제 풀이에서 중요부분은 아래와 같다.

1) while문은 항상 참으로 둠.

2) 이 때 i=2로 가장 작은 소수로 시작함.

3) 2로 나누어 떨어지면 N값을 N/2 연산함. 그리고 나누어졌으므로 2를 출력함.

4) 그리고 다시 while문으로 들어와 다시 N/2된 값을 2로 나눠 봄. 이때 나누어지면 N/2를 다시 2로 나누어 연산함. 그리고 나누어졌으므로 2를 출력함.

3) 만약 나누어 떨어지지 않으면 i=2에서 i++;하여 i를 3으로 올림.

 

즉, 최대한 나누어질때까지는 while문으로 계속해서 나누는 것임. 그리고 출력하는 것임.

더 이상 나누어 떨어지지 않을 때는 나누는 값을 1 올려서 다시 나누어 보는 것임.

 

이런 식으로 나누면 소인수 분해가 가능함.

예를 들어 72의 경우 2, 2, 2, 3, 3으로 출력되는 것을 볼 수 있음. 2를 3번 나누고 더 이상 안 나누어지니 3으로 나누기 시작한 것임.

	i=2;
	while(1)
	{
		if (N%i==0)
		{
			N/=i;
			cout<<i<<endl;
		}
		else i++;
		
		if (N==1) break;
	}

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10000010
using namespace std;

int main()
{
	int N, tmp, i;
	cin>>N;
	
	i=2;
	vector<int> prime(N+1);
	while(1)
	{
		if (N%i==0)
		{
			N/=i;
			cout<<i<<endl;
		}
		else i++;
		
		if (N==1) break;
	}
	return 0;
}