k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT)

원본 : https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

 

풀이

class Solution {
    public int solution(int n, int k) {
        int primeCnt = 0;
        String strN = fn(n, k);

        for (String strP : strN.split("0+")) {
            if (!strP.isEmpty() && isPrime(Long.parseLong(strP))) {
                primeCnt++;
            }
        }

        return primeCnt;
    }

    public String fn(int num, int k) {
        StringBuilder sb = new StringBuilder();

        while (num > 0) {
            sb.append(num % k);
            num /= k;
        }

        return sb.reverse().toString();
    }

    public boolean isPrime(long num) {
        if (num < 2) {
            return false;
        }

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

        return true;
    }
}