[백준/BOJ] 11653번 소인수분해 (C/C++)

백준 온라인 저지(BOJ) 11653번 소인수분해

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

11653번: 소인수분해

* 사용언어 : C언어, C++

 

1. 문제

정수 N 을 소인수 분해하여 오름차순으로 출력

 

2. 풀이

n 을 p 로 나누었을 때 나누어 떨어지는 경우 (n % p == 0)

p 를 출력하고 n 을 p 로 나눕니다.

그리고 더 이상 나누어 떨어지지 않으면 p 를 1 증가시키고 반복합니다.

 

소인수분해의 특성 상 소수로만 나누고 출력해야 한다는 점이 어렵게 느껴지지만,

사실 낮은 수부터 연산을 하기 때문에 소수가 아닌 수는 출력될 수 없습니다.

 

예를 들어 4 로 나누어 떨어지는 수라면 이미 p == 2 인 시점에 2번 나누게 되므로

4로는 나누어 떨어질 수 없습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11653_소인수분해
1112KB	28ms
*/
#include <cstdio>

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n;
	scanf("%d", &n);

	int p = 2;
	while (n > 1) {
		while (n % p == 0) {
			n /= p;
			printf("%d\n", p);
		}
		++p;
	}
	return 0;
}

* prime number(소인수)의 약자를 변수명(p)으로 사용했습니다.