[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 소인수분해 (11653)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 소인수분해 (11653)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 소인수분해 (11653)

 

---

 

11653번: 소인수분해

[ 문제 ]

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

[ 입력 ]

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

[ 출력 ]

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

 

---

[ 코드 ]

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N; // 정수 N
	cin >> N;

	// 소인수 : 인수 중에 소수인 것
	for (int i = 2; i*i <= N; i++) // N의 소수가 되려면, 그 소수는 N의 루트보다는 작아야함. (마지막 남은 소수(인자) 제외)
	{
		while (N%i == 0) // 나누어 떨어진다면
		{
			cout << i << '\n';
			N /= i; // 같은 값으로 나누기
		}
		// 나누어 떨어지지 않는다면 탈출
	}

	if (N>1) // 나머지 남은 몫이 1이 아니면 출력한다. (1이면 출력하지 않는다)
		// 1이 아닌 것이 남으면, 이 수는 소수이다.
	{
		cout << N << '\n';
	}
	return 0;

}