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

앞선 소수 문제들을 풀었다면 무난하게 풀 수 있는 문제이다.

 

Point

n <= 100000이기 때문에 반복문을 통해 이 문제를 가능한 빨리 풀려면,

반복문의 조건을 i < n이 아닌 i * i < n+1로 주어야 할듯하다.

 

n % i == 0이라면 인수 i로 나누어지기 때문에 i를 출력하고,

피인수 n은  n/=i로 값을 바꾼다.

하나의 인수로 여러 번 나누어지는 경우가 있기 때문에 이때 i를 미리 차감해야 한다.

 

#include <stdio.h>

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

	for (i = 2; i * i < n+1; i++)
	{
		if (n % i == 0)
		{
			printf("%d\n", i);
			n /= i--;
		}
	}
	if (n != 1) printf("%d\n", n);

	return 0;
}