소인수분해 (자바, Java)

따로 소인수분해를 하지 않고, 소수를 뽑아 해당 소수로 나눠지는지 판별해서 값을 넣는 식으로 진행했습니다.

소수판별은 에라토스테네스의 체를 이용.

갯수가 가변적이라, queue로 받은 뒤 확정되면 배열에 하나씩 넣었습니다.

 

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[] solution(int n) {
        int[] answer = {};
        boolean[] pn = new boolean[n+1]; // 소수판별배열
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i=0; i<=n; i++) {
        	if (i<=1) {
        		pn[i] = true;
        		continue;
        	}
        	
        	if (pn[i]) {
    			continue;
    		}
        	
        	for (int j=i*i; j<=n; j+=i) {
        			 pn[j] = true;
        	}
        }
        
        for (int i=2; i<=n; i++) {
           	if (!pn[i] && n%i==0) {
           		queue.add(i);
           	}
        }        
        
        int l = queue.size(); // 소인수의 양
        answer = new int[l];
        
        for (int i=0; i<l; i++) {
        	answer[i] = queue.poll();
        }        
        return answer;
    }
}