[백준/C언어] 11653번 - 소인수분해

백준 웹사이트 "11653번 - 소인수분해" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

11653번: 소인수분해

---

소스 코드

#include <stdio.h>

int main(void){
    int N;
    scanf("%d", &N);

    while(N>1){
        for(int i=2; i<=N; i++){
            if(N%i==0){
                printf("%d\n", i);
                N = N/i;
                break; //다시 2부터 시작하기 위해
            }
        }
    }
}

---

문제 풀이

  중학교 때 배운 뒤로 아주 오랜만에 '소인수분해'라는 단어를 본 것 같습니다. 손에 연필을 잡고 열심히 소인수분해를 하던 기억이 있는데, 이 코드만 있으면 이제 다시는 소인수분해를 하지 않아도 됩니다ㅎㅎ.

  원리는 간단합니다. 우선, N을 나누는 가장 작은 소인수를 찾을 때까지 2부터 차례로 N을 나누어봅니다. 소인수를 찾으면 N을 그 소인수로 나눈 후, 그 값을 N에 다시 저장합니다. 이를 반복하다보면, N은 점점 작아지겠죠? 어느 순간, N 자체가 소수가 되어 N을 나누는 수는 N 자신 밖에 없게 됩니다. 따라서 N을 N으로 나누어 N에 1이 저장 되고, N=1은 while 루프의 조건문(N>1)을 만족하지 못하여 코드가 종료됩니다.

  한 가지만 추가로 설명하자면, Line 8에서 N의 소인수를 찾을 때, 2부터 N까지 모두 시도합니다. 실제 소인수분해를 할 때는, 소수가 아닌 수는 시도를 하지 않고 소수만 시도를 해보죠. 예를 들어 2, 3이 소인수가 아니었다면 그 다음으로는 5를 시도하지, 4를 시도하지 않습니다. 원칙적으로는 이런 방식을 따르는 것이 맞지만, 실제로는 4로 나누어떨어질 수였다면 앞의 2에서 이미 걸렸을 것이기에 4로 절대 나누어떨어지지 않을 것이라고 확신할 수 있습니다. 따라서 편의성을 위해 소수들만 따로 선별하여 나누어보지 않고, 2부터 N까지의 수들을 차례로 검사해봐도 괜찮습니다.