소인수분해 문제풀이

주어진 수의 소인수를 오름차순 정렬하여 반환

 

public int[] solution(int n) {

Set<Integer>set = new HashSet<Integer>();

for (int i = 2; i <= n; i++) {

while(n%i==0) {

n/=i;

set.add(i);

}

}

int[] a = new int[set.size()];

Iterator<Integer> it = set.iterator();

for (int i = 0; i < a.length; i++) {

a[i]=it.next();

}

Arrays.sort(a);

return a;

}

2부터 n까지 수를 나누는데 

한번 나눌때 나눠질때까지 계속 나눠야 소인수만 구해진다 그렇지 않으면 소인수의 배수들이 걸러지지 않는다. 

나눌때마다 i를 set에 넣기 때문에 set은 중복을 거르는 Set으로 하였다. 

Set은 순서가 없기 때문에 오름차순 정렬을 위해 배열로 변경하였다.