[C]백준 09.기본수학2: 11653

백준 11653

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int n;
	scanf("%d", &n);
	int divisor = 2;
	if (n != 1) {
		while (n != 1) {
			if (n % divisor == 0) {
				n /= divisor;
				printf("%d\n", divisor);
			}
			else {
				divisor++;
			}
		}
	}
	return 0;
}

손으로 소인수분해를 할 때처럼 n을 2로 나누다가 나누어떨어지지 않으면 3으로, 또 나누어떨어지지 않으면 5로 나누는 것처럼 문제를 풀려고 생각했다.

divisor를 2로 설정하여 n이 1이 되지 않을때까지 반복하는데 만약 n이 divisor로 나누어떨어진다면 n에는 n을 divisor로 나눈 몫을 넣고 divisor 값을 출력한다. 만약 n이 divisor로 나누어떨어지지 않는다면 divisor를 1증가시켰다.

divisor를 1씩 증가시키면 divisor가 항상 소수이지는 않게 된다. 하지만 만약 divisor가 소수가 아니라면 n이 divisor로 나누어떨어지지 않을 것이고 따라서 소수가 아닌 divisor가 출력되는 일은 없을 것이다. 왜냐하면 n은 divisor의 소인수로도 나누어떨어지지 않았기 때문에 그 소인수의 배수인 값까지 divisor가 증가해온 것이기 때문이다. 만약 n이 14라면 divisor는 2였을때 출력되고 n은 14/2의 몫인 7이 된다. 다시 divisor는 3,4,5,6을 거쳐 7일때 출력될 것이다. 비록 divisor는 소수가 아닌 4, 6인 값을 거치지만 이때의 n값 7이 4의 소수인 2로도 나누어떨어지지 않고, 6의 소수인 2, 3으로도 나누어떨어지지 않았기에 당연히 4, 6으로도 나누어떨어지지 않을 것이고 따라서 소수가 아닐때의 divisor값을 출력되지 않는다.