백준 온라인 저지의 11653번 소인수분해 문제입니다.
[링크] https://www.acmicpc.net/problem/11653
문제 조건과 설명
- 정수 N (1 이상 10,000,000 이하)이 주어지고 그 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력합니다.
Input
첫째 줄에 N이 주어집니다. (1<=N<=10,000,000)
Output
소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력합니다.
생각한 아이디어
나누는 숫자는 2부터 시작합니다.
그리고 N을 나누는 숫자(div)로 나누어 나머지가 0이면 나누는 숫자(div)를 즉시 출력하고, N을 div로 나눈 다음, 다시 그 수가 나머지가 0인지 판별하는 과정을 반복했습니다.
만약 나머지가 0이 아니라면, 나누는 숫자(div)만 1 증가시켜 과정을 반복합니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main() {
int div, N, temp;
cin >> N;
div = 2;
temp = N;
while (temp != 1) {
// 나뉘어 질 경우, 출력한 다음 그 수를 div로 나눈다.
if (temp % div == 0) {
printf("%d\n", div);
temp = temp / div;
}
// 나뉘지 않았을 경우, 나누는 숫자만 증가시킨다.
else {
div += 1;
}
}
}