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

www.acmicpc.net/problem/11653

11653번: 소인수분해

문제

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

입력

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

출력

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

---

풀이

Algorithm

1. 변수 설명
   • N : 입력받을 정수를 저장합니다.
   • i : N의 인수를 찾아내는 변수입니다. / N의 인수라면 cout시키고, 아니라면 1 증가시켜줍니다. / 처음에 2로 초기화 해줍니다.
2. 알고리즘 설명
   • N이 1이 될 때까지 인수가 될 수 있는 수로 나누어보는 알고리즘 입니다.
   • 예를 들어 N이 18이면 18 --2로나눔--> 9 --3으로나눔--> 3 --3으로나눔--> 1이 되어 while문을 빠져나오겠죠?
   • 인수를 찾는 역할을 하는 변수가 바로 i입니다. N을 i로 나눈 나머지가 0이라면, i가 N의 인수라는 뜻이니 i를 cout해주고 N에 N/i한 값을 저장해줍니다.
   • 그렇지 않다면 i를 1 증가시켜 다시 그 수가 N의 인수인지 판별합니다.
   • 이 과정을 while문을 빠져나올 때까지 반복합니다.

code

#include <iostream>
using namespace std;

int main() {
	int N, i = 2;
	cin >> N;
	while (N != 1) {
		if (N % i == 0) {
			cout << i << '\n';
			N /= i;
		}
		else
			i++;
	}
	return 0;
}