PGM 92335 k진수에서 소수 개수 구하기

문제 접근

- 복잡해보이지만, 실질적으로는 0으로 split해서 나누었을 때에 나눠지는 숫자들이 몇개 있는지 출력하는 문제이다.

 

헷갈렸던 점

- 1번 문제에서 시간초과가 나서 보니깐, 소수를 구할 때 소수 m만큼 돌 필요 없이, m의 거듭제곱근까지만 돌면 된다고 한다. 

그래서 Math.sqrt(m)까지만 돌아주었더니 해결되었다.

- 그리고 for(int i=3; i<=Math.sqrt(m); i+=2){...} 로 구성해주었는데, i+2로 한 이유는 4, 6, 8... 숫자들은 짝수이므로 더이상 나눠줄 필요가 없기 때문이다. i++과 속도를 비교해보았더니 16ms에서 7ms까지 속도를 줄일 수 있었다.

 

소스 코드

class Solution {
    public static int solution(int n, int k) {
        int answer = -1;
        StringBuffer sb = new StringBuffer();

        while(true){
            long remainder = n % k;
            sb.insert(0, remainder);
            n = n / k;

            if(n == 0) break;
        }
        String str = String.valueOf(sb);
        String[] arrStr = str.split("0");
        int cnt = 0;
        for(int i=0; i<arrStr.length; i++){
            if(arrStr[i].equals("")) continue;
            long num = Long.parseLong(arrStr[i]);
            if(num != 1) {
                if(decimal(num)) {
                    // System.out.println(num);
                    cnt++;
                }
            }
        }
        answer = cnt;
        return answer;
    }
    public static boolean decimal(long num){
        for(int i=3; i<=Math.sqrt(num); i+=2){
            if(num%i == 0) return false;
        }
        return true;
    }
}