백준 알고리즘 11653번 소인수분해 (C언어)

브론즈Ⅰ

 

 

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

 

 

풀이 방법

소인수분해란 주어진 숫자를 소수로만 나누어 나타내는 것을 말한다.

 

N을 입력 받고, for문의 i를 2부터 N까지 돌며 N의 가장 작은 소인수를 찾아 출력한 후, N을 그 소인수로 나눈 몫을 N에 대입한다.

 

내 코드

반응형

#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;
}

 

 

코드설명

 

while (n > 1) {
    for (i = 2; i <= n; ++i) {
        if (n % i == 0) {
            printf("%d\n", i);
            n /= i;
            break;
        }
    }
}
 

• 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)가 소수인지를 판별하는 과정을 거치지 않고 코드를 작성하는게 코드의 길이가 훨씬 짧아지는 것 같다.