프로그래머스 - k진수에서 소수 개수 구하기

 

import java.util.*;

public class Main {
	
    static public int solution(int n, int k) {
    	
    	ArrayList<Integer> list = new ArrayList<Integer>();
    	
    	// 1.n을 k진수로 변환
    	int mok = n/k;    	
    	list.add(n%k);    	
    	while(mok != 0) {
    		list.add(mok%k);    		
    		mok = mok/k;
    	}       	
    	StringBuilder sb = new StringBuilder(); 
    	for(int i=list.size()-1;i>=0;i--) {  
    		sb.append(list.get(i)); // 숫자를 문자열로 변환후 결합시킴
    	}
    	String kBaseNum = sb.toString();
    	    	
    	// 2.조건에 맞는 소수 개수 찾기
    	String[] parts = kBaseNum.split("0");    	    	
    	
    	// 3.소수만 추출    	    	
    	int answer = 0;
    	for (String part : parts) {
    		// isEmpty() -> 빈 문자열("")이 있으면 true를 리턴
            if (part.isEmpty()) {
            	continue;
            }
            if (isPrime(Long.parseLong(part))) {
            	answer++;
            }
        }
        
        return answer;
    }
    
    private static boolean isPrime(long number) {
        if (number == 1) {
            return false;
        }
        if (number == 2) {
            return true;
        }
        if (number % 2 == 0) {
            return false;
        }
        // 1이 아닌 홀수 중에서 소수 판별하기
        // ex) 3,5,7의 제곱근 2.xxx
        // 9의 제곱근 3 -> 제곱근 3이하의 수들에서 어떤 홀수가 9의 약수인지 체크
        // 1,3 -> 3이 9의 약수인지 체크
        // 15의 제곱근 3.xxx -> 제곱근 3이하의 수들에서 어떤 홀수가 15의 약수인지 체크
        // 1,3 -> 3이 15의 약수인지 체크
        
        // 결론 : N이 소수가 아닐 조건은 N의 제곱근 이하의 수 중 하나가 N의 약수이어야 함(단,1은 제외)
        // 모든 약수가 제곱근보다 크다면 이 약수들을 두 개 조합하여 n을 만들었을 때, 그 결과는 n보다 커짐
        // 예를들면, 8의 약수는 1,2,4,8이고 제곱근은 2.xx인데 8의 약수의 조건은 제곱근끼리의 결합 또는 제곱근 보다 작은 수와 제곱근보다 큰 수의 결합으로 이루어진다.
        // 1*8, 2*4
        // 9의 경우는 1,3,9 제곱근은 3 -> 1*9, 3*3
        
        for (long i = 3; i <= Math.sqrt(number); i += 2) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
    
	public static void main(String[] args) {		
		int result = solution(437674, 3);
		System.out.print(result);
	}

}