[C언어] Backjoon_Code 11653, 소인수분해

| 문제

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

 

| 입력

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

 

| 출력

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

 

| 예제 입력 1

72

| 예제 출력 1

2
2
2
3
3

| 예제 입력 2

3

| 예제 출력 2

3

| 예제 입력 3

6

| 예제 출력 3

2
3

 

| 문제의 키 포인트

1. 소인수분해(Prime facotization, integer factorization)란?

▲ 소인수분해, zum, 백과사전

> 소인수분해: 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 합성수를 소수의 곱으로 나타내는 방법을 말한다.

 

2. 그런데 예제 출력 1을 보았을때, 결과값에서는 중복되는 소인수까지 모두 표시해주었다.

 

| 해결방안(Solution)

1. 주어진 정수 N을 가장 작은 소(인)수부터 차례로 나눈다.

> 소(인)수로 이루어진 배열을 만들거나, 소(인)수를 반복문 형태로 만들어서 진행

2. 소수가 아닌 수를 계속 소수로 나눈다.

> 소수인지 여부 판별은 아래의 while() 반복문에서 일괄 진행

3. 몫이 소수가 되면 멈춘다.

> while() 반복문의 조건, 소수인지 판별하는 것은 앞의 문제에서 사용한 코드 활용

4. 몫을 나누었을 때 0이 되는 경우 해당 수를 출력

 

| 소스코드(SourceCode)

// BOJ_11653_Primefacotization, 소인수분해
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	int N, i, j;
	
	scanf("%d", &N);
	
	for (i = 2; i <= N; i++)
	{
		while (N % i == 0)
		{
			printf("%d\n", i);
			N /= i;
		}
	}

	return 0;
}

문제분석시에는 꼭 소(인)수로 나누어줘야 한다는 생각에 사로 잡혀있었는데, 막상 코드를 짜다보니 그럴 필요가 없겠다는 생각이 들었습니다. 결과적으로 수를 나누었을 때 0이 된다면 그것이 바로 소(인)수인 것.

해당 내용을 토대로 코드를 작성해보니, 코드도 깔끔했습니다.

 

| 문제출처

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

11653번: 소인수분해