[백준] 11653번 : 소인수분해

문제

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

입력

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

출력

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

예제 입력 1

72

예제 출력 1

2
2
2
3
3

풀이 1 : 가장 단순한 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>


int main() {

	int n;

	scanf("%d", &n);

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

	return 0;
}

알고리즘 [ 접근방법 ]

while문을 이용한 기본적인 소인수 분해이다.

while (n % i == 0) { // n이 소수일때
	n /= i;
	printf("%d\n", i);
}

n이 소수인경우에 실행되게 함으로써 소수로 나누어 떨어질때마다 이를 출력해준다. 그러나 한가지 처리속도 면에서 아쉬운 점이 보인다.

for  (int i =  2; i <= n; i++)

for문을 2부터 n까지 전부 돌리기 때문에 비효율 적이다. 이를 해결하기 위해 제곱근을 활용한 풀이로 다시 풀어보았다.

풀이2 : 제곱근을 활용한 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int main() {

	int n;
	scanf("%d", &n);

	double temp = sqrt(n);

	for (int i = 2; i <= temp; i++) {
		while (n % i == 0) {
			n /= i;
			printf("%d\n", i);
		}
	}

	if (n != 1) printf("%d\n", n);

	return 0;
}

알고리즘 [ 접근방법 ]

double temp = sqrt(n);

for (int i = 2; i <= temp; i++){

temp라는 변수를 하나 설정해 n의 제곱근을 대입해주고 for문을 temp까지만 돌아가도록 설정했다. 제곱근까지만 돌려도 괜찮은 이유는 이전 포스팅인 [백준] 2581번 : 소수에 설명해놨으므로 이를 참고하길 바란다.

그리고! 한가지 예외처리를 꼭 해줘야만 하는 부분이 있다. 사실 이부분 때문에 이 문제를 포스팅한다고 봐도 된다.

if (n != 1) printf("%d\n", n);

n이 1이 아닐때 n을 출력하는 코드인데 이는 제곱근을 사용했기 때문에 넣어줘여만 하는 코드이다. for문이 i=2부터 temp까지 돌아가게 되는데, 만약 n이 6이라고 하면 i=2부터 √6(≒2.xx)까지 for문이 돌아가므로 i=2일때 한번만 for문이 돌아가 6의 소수인 3이 포함되지 않는다. 이런 경우의 예외처리를 위해 위의 코드를 반드시 넣어줘야 한다.