문제 접근

일단 k진수로 바꾸는 과정을 거쳐야 하는데, k진수로 바꾸는건 스택 써서 k씩 나눈 나머지를 계속 추가하고, 스택에서 다시 꺼내서 순서대로 읽으면 된다.

문제에서 원하는건 그냥 0이 나오기 전까지의 연속된숫자들을 십진수로 바라보고 소수판별하라는 것임.

이때, 소수 판별시 에라토스테네스의 체를 쓸까했지만, 문제 유형자체가 어떤 한 소수의 길이가 길어지면 길어지는 그만큼 다른 검사해야할 소수들의 길이가 짧다는 것이므로, 굳이 에라토스테네스의 체를 쓰지 않아도 됨. 다만, 소수 판별시 제곱근(java로 double Math.sqrt(double) 메소드)을 활용하자.

이때, Math.sqrt의 타입에 주의하자. 그리고, 소수 판별시 2~(long)Math.sqrt((double)n) 까지 포함해서 해야하는 것을 잊지말자.

문제 풀이

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        Stack<Integer> stack = new Stack();
        int remain = n;
        while (remain>0) {
            int tmp = remain % k;
            remain = remain / k;
            stack.add(tmp);
        }
        
        long num = 0;
        while(!stack.isEmpty()) {
            int curN = stack.pop();
            if (curN != 0) {
                num=num*10 + curN;
            } else {
                if (num != 0 && isPrime(num)) {
                    answer++;
                }
                num=0;
            }
        }
        
        if (num!=0 && isPrime(num)) {
            answer++;
        }
        return answer;
    }
    
    boolean isPrime(long n){
        if (n==1) return false;
        if (n==2) return true;
        for(int i=2; i<=(long)Math.sqrt((double)(n)); i++) {
            if (n%i == 0) return false;
        }
        return true;
    }
}