[BaekJoon][11635] 소인수분해

BAEKJOON ONLINE JUDGE

11635 소인수분해

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

소인수 분해라고 해서 소수 여부를 판단할 필요는 없다.

2부터 하여 나누어 떨어지는 가장 작은 값이 n이 가지고 있는 소인수이다.

또한, n을 소인수 분해했을 때 나타날 수 있는 인수 중 가장 큰 값은 root(n)이다.

따라서, 2부터 root(n)까지 반복문을 돌면서 

n을 나눌 수 있으면, 나누고, 나눌 수 없을 때까지 계속한다.

#include <stdio.h>
 
void factorize(int n)
{
    int i;
 
    if (n <= 1)    return;
 
    for (i = 2; i <= n; i++) {
        if (n % i == 0) {
            printf("%d\n", i);
            factorize(n / i);
            return;
        }
    }
}
 
int main()
{
    int n;
 
    scanf("%d", &n);
 
    factorize(n);
 
    return 0;
}