[BOJ 백준] 소인수분해(11653) C++

 

링크 : https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

문제 설명 : 

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력 : 

 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

예제 입력 : 

72

예제 출력 : 

2
2
2
3
3

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 소인수분해 11653
#if 1
#pragma warning(disable:4996)
#include <cstdio>

using namespace std;

int n;

int main() {

	// 1. 입력
	//freopen("input.txt", "r", stdin);
	scanf("%d", &n);

	for (int i = 2; i <= n; i++)
	{
		if (n % i == 0)
		{
			printf("%d\n", i);
			n /= i;
			i = 1;		// i - 2부터 reset
		}
	}
	return 0;
}
#endif