백준 11653 : 소인수분해

★★☆☆☆

굳이 소수의 개념까지 가지 않고도 풀 수 있는 문제

<나의 풀이>

#include <iostream>
using namespace std;
int main() {
	long long n;
	cin>>n;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int q = 2;
	while (n >1) {
		if (n%q == 0) {
			cout << q << "\n";
			n = n / q;
		}
		else { //나누어지지 않으면 다음 숫자로(낮은 수부터 하므로 모두 소수)
			q++;
		}
	}
	return 0;
}

기존에는 소수를 모두 구한후에 다음 소수를 찾아서 나누는 과정을 거쳤는데,
굳이 그럴필요 없이 계속 숫자를 증가시키기만해도 되는 것을 발견했다.
낮은 숫자부터 접근하므로, 6으로 나누게 될 일은 없는 것이다.

그런데 왜 소수를 직접 구한 경우가 더 빠른걸까?

<다른 사람의 풀이>

알고리즘 상에는 차이가 없지만 출력을 나처럼 그때그때 하는것이 아니라,
vector에 담은 후, 하나씩 출력하는 방식을 사용했다.
코드 상으로는 더 길어질지 모르지만 시간은 훨씬 덜걸렸다.

https://vipeveloper.tistory.com/149

1. 현재코드
2. vector에 담아서 출력하는 코드
3. 소수를 직접 구하여 나누는 코드