Programmers - k진수에서 소수 개수 구하기 with JAVA

 

문제

N(1 <= N <= 1,000,000), K(3<=K<=10)이 주어진다.

이때, N을 K진법의 수로 바꾸고 0을 제외한 수들 중 소수의 개수를 구하라. 이때, 수는 0을 포함할 수 없다.

 

 

 

로직

1. 숫자를 K진법 수로 변환한다.

-> StringBuilder를 사용하여 우선적으로 진법으로 변환한 수를 구한다.

 

2. 0을 기준으로 해당 수를 분리한다.

-> split("0")을 통해 분리하고 String[]에 담는다.

 

3. 값마다 소수임을 체크하여 소수의 개수를 구한다.

-> 2번 과정에서 빈 String이 생길 수 있으므로 length()가 0이라면 체크하지 않는다.

-> 소수 체크시 Long처리를 해야한다.

(N의 최대는 100만이고 K의 최소는 3이다. 따라서 3진법으로 100만을 나타낸다면 숫자가 굉장히 커지고 int로 담아낼 수 없다.)

-> 소수 체크는 해당 값의 제곱근 + 1까지 구하고 이때까지 해당 수를 나머지 없이 나눌 수 없다면 소수이다.

-> 1은 소수가 아니다.

 

 

항상, 런타임 오류가 발생하면 웬만하면 범위 초가인 듯 하다.

 

 

코드

import java.util.*;
class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        StringBuilder check = new StringBuilder();
        while(true){
            check.insert(0, String.valueOf(n%k));
            n /= k;
            if(n == 0){
                break;
            }
        }
        String[] values = check.toString().split("0");
        for(String value : values){
            if(value.length() == 0){
                continue;
            }
            if(find(value)){
                answer += 1;
            }
        }
        return answer;
    }
    public static boolean find(String value){
        long new_value = Long.parseLong(value);
        if(new_value == 1){
            return false;
        }
        Long max = (long)Math.sqrt(new_value)+1;
        for(long i=2; i<max; i++){
            if(new_value % i == 0){
                return false;
            }
        }
        return true;
    }
}