링크

import java.util.Stack;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        boolean[] isPrime = new boolean[n + 1];
        Stack<Long> stack = new Stack<>();

        initStack(stack, n, k);

        long number = 0;

        while (!stack.isEmpty()) {
            long pop = stack.pop();
            if (pop == 0) {
                if (isPrime(number)) answer++;
                number = 0;
                continue;
            }
            number = number * 10 + pop;
        }

        if (isPrime(number)) answer++;

        return answer;
    }

    public static boolean isPrime(long number) {
        if (number < 2) return false;
        if (number == 2) return true;
        if (number % 2 == 0) return false;

        for (long i = 3; i <= Math.sqrt(number); i += 2) {
            if (number % i == 0) return false;
        }

        return true;
    }

    public static void initStack(Stack<Long> stack, int n, int k) {
        while (n > 0) {
            stack.push((long) (n % k));
            n /= k;
        }
    }
}

다른방식

이게 좀더 좋아보인다.

import java.util.*;

class Solution {
    public static int solution(int n, int k) {
        List<String> nums = init(n, k);
        int answer = 0;

        for (String s : nums) {
            if (isPrime(Long.parseLong(s))) {
                answer++;
            }
        }

        return answer;
    }

    private static boolean isPrime(long num) {
        if (num == 1) {
            return false;
        }

        for (int i = 2; i <= (int)Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }

    private static String toBinary(int n, int k) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            sb.append(n % k);
            n /= k;
        }
        return sb.reverse().toString();
    }

    private static List<String> init(int num, int binary) {
        StringTokenizer st = new StringTokenizer(toBinary(num, binary), "0");
        List<String> nums = new ArrayList<>();

        while (st.hasMoreTokens()) {
            nums.add(st.nextToken());
        }

        return nums;
    }
}