[백준 2312] 수 복원하기

문제 출처: https://www.acmicpc.net/problem/2312

소인수분해의 전형적인 코드라고할 수 있습니다.

알고리즘은 다음과 같습니다.

m이 2부터시작하므로 n을 최대한 m으로 소인수분해하고 끝났을 때 m과 m으로 소인수분해한 횟수를 출력하고

n이 1될 때 까지(소인수분해가 끝날 때까지) m++하고 cnt=0으로 초기화하여 다시 소인수분해합니다.

n이 1일때 소인수분해가 끝난다는 것을 이용하면 쉽게풀 수 있습니다.

#include<iostream>
using namespace std;
int main()
{
	int n, t;
	cin >> t;
	while (t--)
	{
		int cnt = 0;
		cin >> n;
		//소인수분해를 시작할 값m-> n으로 m부터나누겠다.
		int m = 2;
		while (1) {
			//n=6 m=2;
			if (n % m == 0) {
				n /= m;
				cnt++;
			}
			//45행 마치고 n=3, m=2;
			else {
				if (cnt > 0) cout << m << " " << cnt << endl;
				//n==1일떄 소인수분해 끝난거라 break;
				if (n == 1) break;
				//m=2의경우 소인수분해끝나서 m초기화시킴
				cnt = 0;
				m++;
			}
		}
	}
}