[2022 KAKAO BLIND RECRUITMENT] k진수에서 소수 개수 구하기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92335

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 소수를 구하는 알고리즘과 진수를 구하는 방법에 대해 알고 있다면 쉽게 풀 수 있습니다. 전체적인 풀이는 다음과 같습니다.

1. 주어진 n을 k진수로 만든다
   --> String num = Integer.toString(n,k)
2. 0을 기준으로 파싱한다
   --> String[] arr = num.split("0")
3. 파싱한 수를 소수인지 아닌지 체크한다

소수 체크 알고리즘은 크게 에라토스테네스의 체 방식과 2부터 루트n까지 나누어 나머지가 0이 아닌 수를 선택하는 방식이 있습니다. 이 문제의 경우 파싱된 수가 Int 범위를 넘을 수 있기 때문에 첫 번째 방식으로 진행하지 않고 두 번째 방식으로 진행했습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    static boolean isPrimeNum(long num){
        if(num==1) return false;
        if(num==2) return true;
        
        for(int i=2;i<=(int)Math.sqrt(num);i++){
            if(num%i==0) return false;
        }
        return true;
    }
    
    public int solution(int n, int k) {
        // k진수로 변환 및 0으로 파싱
        int answer = 0;
        String num = Integer.toString(n,k);
        String[] arr = num.split("0");
        
        for(int i=0;i<arr.length;i++){
            if(arr[i].equals("")) continue;
            
            long curr = Long.parseLong(arr[i]);
            if(isPrimeNum(curr)) answer++;
        }
        
        return answer;
    }
}