[Programmers] #120852 - 소인수분해 [Java][C++][Python]

문제 링크

---

1. 아이디어

x를 2부터 1씩 늘려가며 n이 x로 나누어떨어지는지 확인한다. 나누어떨어지면 x는 n의 소인수이므로 결과에 담고, 더 이상 나누어떨어지지 않을 때까지 n을 x로 계속 나눠 같은 소인수의 중복을 없앤다. x를 작은 값부터 훑기 때문에 x가 합성수가 될 즈음에는 그 약수인 더 작은 소수들로 n이 이미 모두 나뉘어 n이 x로 나누어떨어지지 않으므로, 별도의 소수 판정 없이도 소인수만 오름차순으로 모인다. n이 1이 되면 모든 소인수를 찾은 것이다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(\log N)$

($N$ = 입력값 n. n이 소수이면 x가 n까지 증가한다. 결과 배열의 크기는 서로 다른 소인수의 개수로 $O(\log N)$이다)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int n) {
        List<Integer> list = new ArrayList<>();
        int x = 2;

        while (n > 1) {
            if (n % x == 0) {
                list.add(x);
                while (n % x == 0) {
                    n /= x;
                }
                continue;
            }

            x++;
        }

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int n) {
    vector<int> v;
    int x = 2;

    while (n > 1) {
        if (n % x == 0) {
            v.push_back(x);
            while (n % x == 0) {
                n /= x;
            }
            continue;
        }

        x++;
    }

    return v;
}

def solution(n):
    lst = []
    x = 2

    while n > 1:
        if n % x == 0:
            lst.append(x)
            while n % x == 0:
                n //= x
            continue

        x += 1

    return lst

---