[C++] 백준 11653

백준의 11653번 문제 소인수분해이다.

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

11653번: 소인수분해

---

 < 문제 >

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

 

 < 예제 >

 

소인수 분해를 하는 문제이다.

그 전에 소인수 분해에 대해 간단히 설명하자면 1보다 큰 자연수를소인수(소수 + 인수)들만의 곱으로나타내는 것이다.

예시로 40을 들자면 다음과 같이 표현된다.

이렇게 40은 2, 2, 2, 5의 소인수들의 곱으로 나타낼 수 있다.

 

예제를 살펴보면 72는 2 * 2 * 2 * 3 * 3으로 나타낼 수 있는 것이다.

 

먼저 for문만을 사용한 방식이다.

#include <iostream>
using namespace std;

int main() {

	int t;
	cin >> t;

	if (t == 1) {
		return 0;
	}

	for (int i = 2; i <= t;) {
		if (t % i == 0) {
			cout << i << endl;
			t /= i;
		}
		else
			i++;
	}

}

1의 경우 아무것도 출력되지 않아야 하므로 return 0을 하였다.

소인수 분해의 경우 for문을 사용하기 위해서는 이렇게 사용해야 한다.

예시로 든 40의 경우도 2 * 2 * 2 * 5로 나타내지는데 한번 반복 후 3으로 증가해버린다면 표현할 수 없기 때문이다.

해당 수랄 i로 나눴을 때 딱 나눠지는 경우에 그 때의 i값을 출력하게 하였고 그다음에 계산될 수는 i로 나눠진 값이 되기 때문에 t /= i가 들어간다.

그리고 더이상 나눠지지 않는 경우에는 i를 증가시켜 다음 숫자로 나눌 수 있게 하였다.

 

다음은 while문을 사용한 코드이다.

#include <iostream>
using namespace std;

int main() {

	int t;
	cin >> t;

	if (t == 1) {
		return 0;
	}

	for (int i = 2; i <= t; i++) {
		while (t % i == 0) {
			cout << i << endl;
			t /= i;
		}
	}
}

for문과 똑같다.

1일 경우 return 0을 해서 프로그램을 종료시킨다.

그리고 while문을 해당 수를 i로 나눴을 때 0이 나오는 경우 출력해주고 조건식이 거짓인 경우에 while문을 종료한다.

while문이 종료되면 for문을 통해 i가 1 증가된 값으로 t를 나눈다.

 

2가지 방식을 설명했는데 똑같은 방법으로 구하지만 속도의 차이가 난다.

for문만을 사용했을 때에는 28ms에 메모리를 2020KB를 사용하지만

while을 사용했을 경우에 32ms의 속도에 41040KB를 사용한다.

 

while문보다는 for문만 사용하는 것이 메모리를 효율적으로 사용하며 빠르게 처리하기 때문에 가능하다면 for문만 사용하여 문제를 풀어보도록 해야겠다.

 

아래는 for, while, iterator를 비교한 블로그의 글인데 한번 봐두면 좋을 것 같아서 추가해보았다.

https://3colored.tistory.com/5

반복문 속도 비교 (while, for, iterator)