백준 알고리즘 단계별로 풀어보기/약수, 배수와 소수
백준 알고리즘 11653번 소인수분해 (C언어)
MNMNWVWV
2023. 3. 10. 17:25
728x90
반응형
브론즈Ⅰ
https://www.acmicpc.net/problem/11653
11653번: 소인수분해
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
www.acmicpc.net
풀이 방법
소인수분해란 주어진 숫자를 소수로만 나누어 나타내는 것을 말한다.
N을 입력 받고, for문의 i를 2부터 N까지 돌며 N의 가장 작은 소인수를 찾아 출력한 후, N을 그 소인수로 나눈 몫을 N에 대입한다.
내 코드
반응형
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#pragma (disable:4996)
#include <stdio.h>
int main() {
int n, i;
scanf("%d", &n);
while (n > 1) {
for (i = 2; i <= n; ++i) {
if (n % i == 0) {
printf("%d\n", i);
n /= i;
break;
}
}
}
return 0;
}
|
cs |
코드설명
1
2
3
4
5
6
7
8
9
10
|
while (n > 1) {
for (i = 2; i <= n; ++i) {
if (n % i == 0) {
printf("%d\n", i);
n /= i;
break;
}
}
}
|
cs |
위 코드는 입력된 수 n을 소인수분해하는 부분입니다.
- while 루프는 n이 1보다 큰 동안 반복됩니다. 즉, n을 1로 소인수분해할 때까지 반복됩니다.
- for 루프는 2부터 n까지의 숫자를 i로 나누어 보는 것입니다.
- if 문은 n을 i로 나누어 떨어지게 만드는 첫 번째 i 값을 찾습니다. 그러면 i는 n의 소인수 중 하나이므로 출력하고 n을 i로 나눕니다.
- break문은 for 루프를 빠져나오기 위해 사용됩니다. if 문 안에 있는 break 문은 n의 가장 작은 소인수를 찾았을 때 더 이상 for 루프를 돌 필요가 없기 때문입니다.
위 코드에서 printf("%d\n", i); 라인은 찾은 소인수를 출력합니다.
예를 들어, n이 24인 경우, i 값은 다음과 같이 변합니다.
- 2: 24를 2로 나누면 나머지가 0이므로 i 값인 2를 출력하고, n은 12가 됩니다.
- 2: 12를 2로 나누면 나머지가 0이므로 i 값인 2를 출력하고, n은 6이 됩니다.
- 3: 6을 2로 나누어 보고 나머지가 0이 아니므로, 3으로 나누어 봅니다. 6을 3으로 나누면 나머지가 0이므로 i 값인 3을 출력하고, n은 2가 됩니다.
- 2: 2를 2로 나누면 나머지가 0이므로 i 값인 2를 출력하고, n은 1이 됩니다.
따라서, n을 소인수분해한 결과는 2 x 2 x 2 x 3 = 24 입니다.
느낀점
숫자(i)가 소수인지를 판별하는 과정을 거치지 않고 코드를 작성하는게 코드의 길이가 훨씬 짧아지는 것 같다.
728x90