Lv0 - 소인수분해

문제설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

 

입출력 예

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

 

생각정리

소인수 분해의 기본적인 아이디어는 다음과 같다

1.  i=2로 시작하여 i++ 하면서 n%i == 0 인지 체크한다.
2. n%i==0이 성립하는 경우 i를 소인수로 등록한 후 n은 i로 나눈 값을 저장하고
    i는 i++ 하지 않고 i부터 다시 시작한다.
3. n이 1이 될 때까지 위 과정을 반복한다.

 

1. 위의 조건을 코드로 구현하면서도, 오름차순으로 정렬해야하기위해서 ArrayList 자료구조를 사용한다.

List<Integer> li = new ArrayList<>();

for (int i = 2; i <= n; i++) {
    if (n%i == 0) {   
        li.add(i);	// 소인수(i)를 ArrayList에 저장
        while (n % i == 0) { // i 중복입력 막기위해 i로 끝까지 나누어준다.              
            n /= i;
        }
    }
}

2. ArrayList에 저장된 소인수 들을 정렬한뒤 배열을 만들고 리턴한다.

int [] result = new int[li.size()];

//ArrayList 값을 배열로 
for (int i=0; i<li.size(); i++) {
    result[i] = li.get(i);
}

Arrays.sort(result); //정렬

return result;