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

1. 문제이해

11653번: 소인수분해 (acmicpc.net)

11653번: 소인수분해

 

정수 N을 입력받아, 해당 정수를 소인수분해한 결과를 오름차순으로 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

정수 N을 입력받아 소인수분해하는 문제이다.

예를 들어 72의 경우, 소인수 분해하게 되면 2 x 2 x 2 x 3 x 3 이고,

오름차순으로 출력해야하므로 한줄씩 차례대로 2 2 2 3 3을 출력하면 된다.

또 다른 예로 150의 경우, 2 x 3 x  5 x 5 이므로, 차례대로 2 3 5 5 를 출력하면 된다.

위와 같이 인수들을 출력하기 위해, 작은 인수부터 시작해서 점차 숫자를 늘려나가며 N의 인수를 찾아나가는 방법을 이용했다.

 

 

 

3. 소스코드

#include <iostream>
using namespace std;

int main() {
	int N;
	// 인수는 2부터 시작
	int factor = 2;
	cin >> N;

	while (N != 1) {	// 1이 되면 더이상 나누지 못하므로 종료
		if (N % factor == 0) {	// 나누어지면(인수이면)
			cout << factor << '\n';
			N = N / factor;
		}
		else {	// 인수를 점차 올려가며 위 if문에서 오름차순으로 출력
			factor++;
		}
	}

	return 0;
}

N을 입력받아 while 문 안의 if문을 통해, 인수이면, 즉 나누어떨어지면 해당 인수를 출력하고,

아니라면 인수의 값을 하나씩 늘려가며 계산해주었다.

N이 1이되면 더이상 나눌수 없으므로 while문을 종료하고,

인수(factor)는 2부터 시작하도록 설정했다. (1부터 시작하면 계속 나누어짐.)

 

 

---

내일이 드디어 정보처리기사 합격발표일이다..

올해들어 가장 긴장되는 순간인것같다..😱

내일은 맘편히 먹고 결과 기다리고.. 일상게시판에 꿀팁이나 적어볼까 생각중이다.

(일상 게시판에 아직 1개도 안올라와있으니 뭔가 허전하달까..ㅎㅎ)

제발 좋은 결과 있기를..🙏🙏