소인수분해

/* 소인수분해

 * 소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다.

 * 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다.

 * 따라서 12의 소인수는 2와 3입니다.

 * 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return

 * 2 ≤ n ≤ 10,000

 *

 * n    result

 * 12   [2, 3]

 * 17   [17]

 * 420  [2, 3, 5, 7]

 */

 

import java.util.*;
public class programmer_0_83 {
    static int a1 = 12; static int a2 = 17; static int a3 = 420; 
    public int getCnt(int n){   //약수의 갯수
        int cnt = 0;
        for(int i=1; i*i <= n; i++){    
            if(n%i == 0){
                cnt++;
                if(i*i < n) cnt ++;
            }
        }
        return cnt;
    }
    public List<Integer> getChk(int n){  //소수 조회
        List<Integer> ar = new ArrayList<>();
        
        for(int i = 2; i <= n; i++){
            if(getCnt(i) < 3)   ar.add(i);
        }
        return ar;
    }
    public List<Integer> solution(int n) {
        List<Integer> answer = new ArrayList<>();
        List<Integer> ar = new ArrayList<>();
        ar = getChk(n);
        
        for(int i = 0; i < ar.size(); i++){
            if(n%ar.get(i) == 0)    answer.add(ar.get(i));
        }
        return answer;
    }
    public static void main(String args[]){
        programmer_0_83 t = new programmer_0_83();
        System.out.println("---------------------------------------");
        System.out.println("result = " + t.solution(a1));
        System.out.println("---------------------------------------");
        // System.out.println("result2 = " + t.solution(a2));
        // System.out.println("---------------------------------------");
    }
}