오랜만에 중학교 수학을 하니 조금 재미있었던 문제다. 숫자를 소수로 나누는 과정이 생각보다 머리를 좀 굴리게 했다. 처음엔 그냥 2부터 시작해서 나누기를 계속했는데, 이건 너무 효율이 떨어지는 것 같았다. 그래서 제곱근까지만 확인하면 된다는 걸 떠올리고 코드를 바꿨다. 근데 여기서 실수가 있었다. 소수를 구할 때 중복을 제대로 안 걸러서 결과에 같은 소수가 여러 번 들어갔다. 그래서 TreeSet을 써서 중복 제거와 오름차순 정렬을 동시에 해결했다.

for(int i = 2; i <= Math.sqrt(n); i++){
    while(n % i == 0){
        set.add(i);
        n /= i;
    }
}
if(n > 1) set.add(n);

이 코드는 제곱근까지만 확인하고, 남은 수가 소수일 경우를 처리하는 게 핵심이었다. 처음엔 n을 계속 나누지 않고 그냥 약수만 구해서 테스트 케이스가 틀렸다. n /= i를 안 했던 게 문제였는데, 디버깅하면서 로직을 하나씩 점검하니까 해결됐다. 이 문제로 자료구조 선택이 얼마나 중요한지 다시 느꼈다. 다음엔 소수 관련 문제 풀 때 제곱근 활용법을 바로 떠올릴 수 있을 것 같다.