[백준] 11653번 : 소인수분해 (C언어 / C99)

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

 

조건 및 입출력

1. 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

2. N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

 

코드 (C99)

#include <stdio.h>

int main()
{
	long long num;
	scanf("%lld", &num);

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

		}
	}

	return 0;
}

 

 

풀이 과정

어떤 수 n과 k에 대하여, 1을 제외하고 n과 k가 나누어 떨어지면 그 수는 소수이다.

그런 의미에서 n을 소수 k의 집합으로 나타낸 것이 소인수분해이다.

 

간단하게 생각하면, 소수 찾기 알고리즘을 이용하여 문제를 푼다.

소수를 하나 찾으면 원래 주어진 수를 나누어 주기만 하면 된다.

 

그러다 원래 주어진 수가 1이 되는 순간 루프를 종료시킨다. (약수의 정의)

 

---

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주세요 :)