백준 소인수분해

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

#include <iostream>
#include <algorithm>
using namespace std;
bool primeN(int n) {
	if (n == 1) return false;
	for (int i = 2; i <= n / 2; i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	int n;
	cin >> n;
	int prime[10000];
	int primeIndex = 0;

	while (n!=1) //나눠지는 수가 1이 아닐 때까지
	{	
		for (int i = 2; i <= n; i++) {
			if (n % i == 0&&primeN(i)) {
				n = n / i;
				prime[primeIndex++] = i;
			}
		}
	}
	if (primeIndex==0&&primeN(n)) //최초 입력값이 소수이면
		cout << n << '\n';
	
	else {
		sort(prime, prime + primeIndex);
		for (int i = 0; i < primeIndex; i++) {
			cout << prime[i] << '\n';
		}
	}
}

오답노트

1. 처음에 while(!primeN(n)) 이라고 작성해서 틀렸다
   이로 인해 마지막 소수가 출력되지 않았다
   ->72=2x2x2x3x3으로 나타낼 수 있는데
   n을 소수로 차례대로 나누다 n=2가 되면 루프를 빠져나간다
   따라서 while(n!=1)이 되야 한다

2. 1일 경우 출력값이 없어야 한다. 따라서 if문에 primeN(n) 조건도 추가해줘야 한다.

3. 시간 초과 문제: primeN(i)는 함수를 호출하므로, if문에 여러 조건을 작성할 때 뒤로 빼야 한다
   ->if (primeN(i)&&n%i==0)